Tương tự như đồ thị, cây cũng là tập hợp các đỉnh và cạnh. Tuy nhiên, trong cấu trúc dữ liệu cây, chỉ có thể có một cạnh giữa hai đỉnh.
Cấu trúc dữ liệu dựa trên cây phổ biến:
Cây nhị phân
Cây tìm kiếm nhị phân
Cây AVL
Cây B
Cây B+
Cây đỏ-đen
Cấu trúc dữ liệu tuyến tính và phi tuyến tính
Bây giờ chúng ta đã biết về cấu trúc dữ liệu tuyến tính và phi tuyến tính, hãy cùng xem những điểm khác biệt chính giữa chúng.
Cấu trúc dữ liệu tuyến tính
Cấu trúc dữ liệu phi tuyến tính
Các mục dữ liệu được sắp xếp theo thứ tự tuần tự, cái này sau cái kia.
Các mục dữ liệu được sắp xếp theo thứ tự không tuần tự (theo thứ bậc).
Tất cả các mục dữ liệu đều có trên một lớp duy nhất.
Các mục dữ liệu có mặt ở các lớp khác nhau.
Có thể duyệt qua trong một lần chạy. Nghĩa là, nếu chúng ta bắt đầu từ phần tử đầu tiên, chúng ta có thể duyệt qua tất cả các phần tử theo trình tự trong một lần chạy.
Nó đòi hỏi nhiều lần chạy. Nghĩa là, nếu chúng ta bắt đầu từ phần tử đầu tiên, có thể không thể duyệt qua tất cả các phần tử trong một lần chạy.
Việc sử dụng bộ nhớ không hiệu quả.
Các cấu trúc khác nhau sử dụng bộ nhớ theo những cách hiệu quả khác nhau tùy theo nhu cầu.
Độ phức tạp về thời gian tăng theo kích thước dữ liệu.
Độ phức tạp về thời gian vẫn giữ nguyên.
Ví dụ: Mảng, Ngăn xếp, Hàng đợi
Ví dụ: Cây, Đồ thị, Bản đồ
1.3.3.Tại sao lại là Cấu trúc dữ liệu?
Kiến thức về cấu trúc dữ liệu giúp bạn hiểu cách thức hoạt động của từng cấu trúc dữ liệu. Và dựa trên đó, bạn có thể chọn đúng cấu trúc dữ liệu cho dự án của mình.
Điều này giúp bạn viết mã hiệu quả về bộ nhớ và thời gian
1.4. Tại sao phải học Cấu trúc dữ liệu và Thuật toán?
Bài viết này dành cho những người mới bắt đầu học thuật toán và tự hỏi liệu nó có tác động như thế nào đến sự nghiệp/kỹ năng lập trình của họ. Bài viết này cũng dành cho những người tự hỏi tại sao các công ty lớn như Google, Facebook và Amazon lại thuê những lập trình viên cực kỳ giỏi trong việc tối ưu hóa thuật toán.
1.4.1. Thuật toán là gì?
Theo nghĩa thông thường, thuật toán không gì khác hơn là đề cập đến các bước để giải quyết một vấn đề. Về cơ bản, chúng là một giải pháp.
Ví dụ, một thuật toán để giải quyết vấn đề giai thừa có thể trông giống như thế này:
Bài toán: Tìm giai thừa của n
Khởi tạo fact = 1 Với mọi giá trị v trong phạm vi từ 1 đến n:: Nhân fact với v fact chứa giai thừa của n
Ở đây, thuật toán được viết bằng tiếng Anh. Nếu nó được viết bằng ngôn ngữ lập trình, chúng ta sẽ gọi nó là code. Đây là code để tìm giai thừa của một số trong C++.
int factorial(int n) { int fact = 1; for (int v = 1; v <= n; v++) { fact = fact * v; } return fact; }
Lập trình là tất cả về cấu trúc dữ liệu và thuật toán. Cấu trúc dữ liệu được sử dụng để lưu trữ dữ liệu trong khi thuật toán được sử dụng để giải quyết vấn đề bằng cách sử dụng dữ liệu đó.
Cấu trúc dữ liệu và thuật toán (DSA) sẽ đi sâu vào các giải pháp cho các vấn đề tiêu chuẩn và cung cấp cho bạn cái nhìn sâu sắc về mức độ hiệu quả khi sử dụng từng giải pháp. Nó cũng dạy cho bạn khoa học về việc đánh giá hiệu quả của một thuật toán. Điều này cho phép bạn chọn ra giải pháp tốt nhất trong số nhiều lựa chọn khác nhau.
1.4.2.Sử dụng Cấu trúc dữ liệu và Thuật toán để Làm cho Mã của bạn có khả năng mở rộng
Thời gian là quý giá.
Giả sử, Alice và Bob đang cố gắng giải một bài toán đơn giản là tìm tổng của 1011 số tự nhiên đầu tiên. Trong khi Bob đang viết thuật toán, Alice đã triển khai nó để chứng minh rằng nó đơn giản như việc chỉ trích Donald Trump.
Thuật toán (của Bob)
Khởi tạo sum = 0 cho mọi số tự nhiên n trong phạm vi từ 1 đến \({10^{11}}\)(bao gồm): thêm n vào tổng tổng là câu trả lời của bạn
Code (by Alice)
int findSum() { int sum = 0; for (int v = 1; v <= 100000000000; v++) { sum += v; } return sum; }
Alice và Bob đang cảm thấy phấn khích vì họ có thể tự xây dựng thứ gì đó của riêng mình trong thời gian ngắn. Hãy lẻn vào không gian làm việc của họ và lắng nghe cuộc trò chuyện của họ.
Alice: Hãy chạy mã này và tìm ra tổng. Bob: Tôi đã chạy mã này cách đây vài phút nhưng nó vẫn không hiển thị kết quả. Có vấn đề gì vậy?
Ồ, có gì đó không ổn! Máy tính là cỗ máy có tính quyết định nhất. Quay lại và thử chạy lại sẽ không có ích gì. Vậy hãy cùng phân tích xem đoạn mã đơn giản này có vấn đề gì.
Hai trong số những tài nguyên có giá trị nhất đối với một chương trình máy tính là thời gian và bộ nhớ.
Thời gian máy tính chạy mã là:
Thời gian chạy mã = số lượng câu lệnh * thời gian thực hiện từng lệnh
Số lượng lệnh phụ thuộc vào mã bạn sử dụng và thời gian thực thi mỗi mã phụ thuộc vào máy và trình biên dịch của bạn.
Trong trường hợp này, tổng số lệnh được thực thi (giả sử là x) là :
x = 1 + (\({10^{11}}\) + 1) + (\({10^{11}}\)) + 1, đó là x = 2 * \({10^{11}}\) + 3
Giả sử rằng máy tính có thể thực hiện y = \(10^8\)câu lệnh trong một giây (có thể thay đổi tùy thuộc vào cấu hình máy). Thời gian chạy mã trên là
Thời gian để chạy y câu lệnh = 1 second Thời gian để chạy 1 câu lệnh = 1 / y seconds Thời gian để chạy x câu lệnh = x * (1/y) seconds = x / y seconds Kể từ đây, Thời gian để chạy câu lệnh = x / y = (2 * 1011 + 3) / 108 (lớn hơn 33 phút )
Có thể tối ưu hóa thuật toán để Alice và Bob không phải đợi 33 phút mỗi lần chạy mã này không?
Tôi chắc chắn rằng bạn đã đoán đúng phương pháp rồi. Tổng của N số tự nhiên đầu tiên được đưa ra theo công thức:
Sum = N * (N + 1) / 2
Chuyển đổi nó thành mã sẽ trông giống như thế này:
int sum(int N) { return N * (N + 1) / 2; }
Mã này thực thi chỉ trong một lệnh và hoàn thành nhiệm vụ bất kể giá trị là bao nhiêu. Giả sử giá trị đó lớn hơn tổng số nguyên tử trong vũ trụ. Nó sẽ tìm ra kết quả trong thời gian ngắn.
Thời gian cần để giải quyết vấn đề, trong trường hợp này, là 1/y (tức là 10 nano giây). Nhân tiện, phản ứng tổng hợp của bom hydro mất 40-50 ns, điều đó có nghĩa là chương trình của bạn sẽ hoàn thành thành công ngay cả khi ai đó ném một quả bom hydro vào máy tính của bạn cùng lúc bạn chạy mã của mình. :
Lưu ý: Máy tính cần một vài lệnh (không phải 1) để tính phép nhân và phép chia. Tôi nói 1 chỉ để đơn giản.
1.4.3.Thêm về khả năng mở rộng
Khả năng mở rộng là quy mô cộng với khả năng, nghĩa là chất lượng của thuật toán/hệ thống để xử lý vấn đề có quy mô lớn hơn.
Hãy xem xét vấn đề thiết lập một lớp học có 50 học sinh. Một trong những giải pháp đơn giản nhất là đặt phòng, lấy bảng đen, một vài viên phấn và vấn đề được giải quyết.
Nhưng nếu quy mô của vấn đề tăng lên thì sao? Nếu số lượng học sinh tăng lên 200 thì sao?
Giải pháp vẫn đúng nhưng cần nhiều nguồn lực hơn. Trong trường hợp này, có thể bạn sẽ cần một căn phòng lớn hơn nhiều (có thể là rạp chiếu phim), màn hình máy chiếu và bút kỹ thuật số.
Nếu số lượng học sinh tăng lên 1000 thì sao?
Giải pháp sẽ thất bại hoặc sử dụng nhiều nguồn lực khi quy mô của vấn đề tăng lên. Điều này có nghĩa là giải pháp của bạn không có khả năng mở rộng.
1.4.4.Vậy thì giải pháp có thể mở rộng quy mô là gì?
Hãy xem xét một trang web như Khanacademy, hàng triệu học sinh có thể xem video, đọc câu trả lời cùng lúc và không cần thêm tài nguyên nào nữa. Vì vậy, giải pháp có thể giải quyết các vấn đề có quy mô lớn hơn trong tình trạng thiếu tài nguyên.
Nếu bạn thấy giải pháp đầu tiên của chúng tôi để tìm tổng của N số tự nhiên đầu tiên, thì giải pháp đó không có khả năng mở rộng quy mô. Đó là vì giải pháp này đòi hỏi sự tăng trưởng tuyến tính theo thời gian với sự tăng trưởng tuyến tính về quy mô của vấn đề. Các thuật toán như vậy cũng được gọi là thuật toán có khả năng mở rộng tuyến tính.
Giải pháp thứ hai của chúng tôi có khả năng mở rộng quy mô rất cao và không cần sử dụng thêm thời gian để giải quyết vấn đề có quy mô lớn hơn. Chúng được gọi là thuật toán thời gian không đổi.
1.4.5. Bộ nhớ đắt tiền
Bộ nhớ không phải lúc nào cũng có sẵn dồi dào. Khi xử lý mã/hệ thống yêu cầu bạn phải lưu trữ hoặc tạo ra nhiều dữ liệu, điều quan trọng đối với thuật toán của bạn là tiết kiệm việc sử dụng bộ nhớ bất cứ khi nào có thể. Ví dụ: Khi lưu trữ dữ liệu về mọi người, bạn có thể tiết kiệm bộ nhớ bằng cách chỉ lưu trữ ngày sinh của họ, không phải tuổi của họ. Bạn luôn có thể tính toán nhanh chóng bằng cách sử dụng ngày sinh và ngày hiện tại của họ.
1.4.6.Ví dụ về hiệu quả của thuật toán
Sau đây là một số ví dụ về những gì thuật toán học tập và cấu trúc dữ liệu cho phép bạn thực hiện:
Ví dụ 1: Bài toán nhóm tuổi
Các bài toán như tìm những người trong một nhóm tuổi nhất định có thể dễ dàng được giải quyết bằng một phiên bản sửa đổi nhỏ của thuật toán tìm kiếm nhị phân (giả sử dữ liệu được sắp xếp).
Thuật toán ngây thơ duyệt qua tất cả những người từng người một và kiểm tra xem họ có nằm trong nhóm tuổi đã cho hay không có thể mở rộng tuyến tính. Trong khi đó, tìm kiếm nhị phân tự nhận mình là thuật toán mở rộng logarit. Điều này có nghĩa là nếu kích thước của bài toán được bình phương, thời gian giải quyết chỉ tăng gấp đôi.
Giả sử, mất 1 giây để tìm tất cả những người ở một độ tuổi nhất định trong một nhóm gồm 1000 người. Sau đó, đối với một nhóm gồm 1 triệu người,
-thuật toán tìm kiếm nhị phân sẽ chỉ mất 2 giây để giải quyết bài toán
-thuật toán ngây thơ có thể mất 1 triệu giây, tức là khoảng 12 ngày
Thuật toán tìm kiếm nhị phân tương tự được sử dụng để tìm căn bậc hai của một số
Ví dụ 2: Bài toán khối Rubik
Hãy tưởng tượng bạn đang viết một chương trình để tìm lời giải cho khối Rubik.
Câu đố dễ thương này có tới 43.252.003.274.489.856.000 vị trí, và đây chỉ là những vị trí! Hãy tưởng tượng số đường đi mà người ta có thể đi để đến được những vị trí sai.
May mắn thay, cách giải quyết vấn đề này có thể được biểu diễn bằng cấu trúc dữ liệu đồ thị. Có một thuật toán đồ thị được gọi là thuật toán Dijkstra cho phép bạn giải quyết vấn đề này theo thời gian tuyến tính. Đúng vậy, bạn nghe đúng rồi đấy. Nghĩa là nó cho phép bạn đạt đến vị trí đã giải trong số lượng trạng thái tối thiểu.
Ví dụ 3: Bài toán DNA
DNA là một phân tử mang thông tin di truyền. Chúng được tạo thành từ các đơn vị nhỏ hơn được biểu diễn bằng các ký tự La Mã A, C, T và G.
Hãy tưởng tượng bạn đang làm việc trong lĩnh vực tin sinh học. Bạn được giao nhiệm vụ tìm ra sự xuất hiện của một mô hình cụ thể trong một chuỗi DNA.
Đây là một bài toán nổi tiếng trong học viện khoa học máy tính. Và thuật toán đơn giản nhất mất thời gian tỷ lệ thuận với
(số lượng ký tự trong chuỗi DNA) * (số lượng ký tự trong mẫu)
Một sợi DNA điển hình có hàng triệu đơn vị như vậy. Ồ! đừng lo lắng. Thuật toán KMP có thể thực hiện việc này trong thời gian tỷ lệ thuận với
(số lượng ký tự trong chuỗi DNA) + (số lượng ký tự trong mẫu)
Toán tử * được thay thế bằng + mang lại rất nhiều thay đổi.
Xem xét rằng mẫu có 100 ký tự, thuật toán của bạn hiện nhanh hơn 100 lần. Nếu mẫu của bạn có 1000 ký tự, thuật toán KMP sẽ nhanh hơn gần 1000 lần. Nghĩa là, nếu bạn có thể tìm ra sự xuất hiện của mẫu trong 1 giây, giờ bạn chỉ mất 1 ms. Chúng ta cũng có thể diễn đạt theo cách khác. Thay vì khớp 1 chuỗi, bạn có thể khớp 1000 chuỗi có độ dài tương tự cùng một lúc.
Và có vô số câu chuyện như vậy...
1.4.7.Lời kết
Nhìn chung, phát triển phần mềm liên quan đến việc học các công nghệ mới hàng ngày. Bạn có thể học hầu hết các công nghệ này trong khi sử dụng chúng trong một trong các dự án của mình. Tuy nhiên, thuật toán thì không như vậy.
Nếu bạn không hiểu rõ về thuật toán, bạn sẽ không thể xác định được liệu mình có thể tối ưu hóa mã đang viết ngay lúc này hay không. Bạn được kỳ vọng là phải biết trước về chúng và áp dụng chúng bất cứ khi nào có thể và quan trọng.
Chúng tôi đã nói cụ thể về khả năng mở rộng của thuật toán. Một hệ thống phần mềm bao gồm nhiều thuật toán như vậy. Việc tối ưu hóa bất kỳ thuật toán nào trong số chúng sẽ dẫn đến một hệ thống tốt hơn.
Tuy nhiên, điều quan trọng cần lưu ý là đây không phải là cách duy nhất để làm cho một hệ thống có thể mở rộng. Ví dụ, một kỹ thuật được gọi là điện toán phân tán cho phép các phần độc lập của một chương trình chạy trên nhiều máy cùng nhau, giúp nó có khả năng mở rộng hơn nữa.
