8 cấu trúc dữ liệu siêu cơ bản mà Dev nào cũng nên biết – Phần 1: Ôn lại về Big-O Notation và độ phức tạp

Bài viết được cho phép bởi tác giả Phạm Huy Hoàng

Thay vì ngồi học mấy công nghệ cao siêu, kì này tụi mình ngồi học lại cơ bản, ôn lại kiến thức về thuật toán, về các cấu trúc dữ liệu thôi nhỉ?

Kiến thức về thuật toán không được dùng hằng ngày trong việc code, nhưng nó giúp bạn viết code tối ưu hơn, xử lý nhanh hơn. Ngoài ra, rất nhiều công ty bây giờ khoái phỏng vấn bằng thuật toán.

Số lượng thuật toán, cấu trúc dữ liệu có rất rất nhiều, kể vài quyển sách chưa hết. Tuy vậy, tụi mình chỉ cần tập trung vào 8 cấu trúc dữ liệu cơ bản này là được!

96,69% các bài phỏng vấn, leetcode, thuật toán … đều dựa trên 8 cấu trúc dữ liệu này, và 1 số biến thể của nó. Nắm vững 8 cấu trúc dữ liệu này, biết cách sử dụng nó là các bạn đã có kiến thức kha khá rồi nhé!

Ôn lại về độ phức tạp của thuật toán

Độ phức tạp của thuật toán (biểu diễn bằng Big-O Notation), là một biểu thức mô tả hành vi thuật toán (ví dụ, về mặt thời gian tính toán hoặc lượng bộ nhớ cần dùng) khi kích thước dữ liệu thay đổi.

Nói đơn giản, Big O mô tả mối liên hệ giữa số lượng phần tử đầu vào và số lượng operation – thời gian chạy, hoặc số lượng bộ nhớ mà thuật toán cần sử dụng.

Nhìn vào hình dưới các bạn sẽ hiểu ngay.

• Với các thuật toán có độ phức tạp là O(n), khi dữ liệu đầu vào có 10 phần tử, chương trình phải chạy 10 operation. Khi số dữ liệu đầu vào tăng gấp đôi, số lượng câu lệnh phải tăng gấp đôi
• Nếu độ phức tạp là O(n²), khi số lượng dữ liệu đầu vào tăng gấp đôi, số lượng câu lệnh phải tăng gấp 2² tức là gấp 4 lần
• Nói túm lại, thuật toán có độ phức tạp càng lớn, khi số lượng dữ liệu càng nhiều hơn lên thì nó sẽ chạy càng chậm.

Ví dụ, với bài toán tìm đường cho người đưa thư qua nhiều thành phố (traveling salesman problem), dùng thuật toán vét cạn có độ phức tạp là O(n!), khi dữ liệu quá nhiều tầm vài ngàn địa điểm thì … siêu máy tính cũng chạy rất lâu.

Xem thêm tuyển dụng Back-end hấp dẫn trên TopDev

Phân biệt time và space complexity

Big O Notation có thể dùng cho cả thời gian chạy – số lượng câu lệnh chạy, cũng như lượng bộ nhớ mà thuật toán cần sử dụng.

Để dễ phân biết, người ta phân ra thành:

• Time Complexity: Số lượng câu lệnh phải chạy – thời gian chạy của thuật toán dựa theo lượng phần tử đầu vào
• Space Complexity: Số lượng bộ nhớ thêm mà thuật toán cần, dựa theo số lượng phần tử đầu vào
• Chữ “độ phức tạp” chính là từ complexity mà ra

Giả sử, các bạn được cho 1 bài toán Two Sum cơ bản:

Cho 1 mảng gồm N số không trùng nhau. Hãy tìm 2 số trong mảng có tổng bằng X

Các bạn có thể giải theo 2 cách:

• Cách 1: Dùng 2 vòng lặp, lặp qua toàn bộ các phần tử của mảng để lấy các cặp.
  • Cách này không tốn thêm bộ nhớ, nhưng time complexity là O(n²), vì ta phải chạy 2 vòng lặp lồng nhau, mỗi vòng lặp gồm n phần tử.
• Cách 2: Duyệt từng phần tử, lưu các phần tử đã duyệt vào 1 set. Mỗi khi gặp 1 phần tử có giá trị A, ta tính ra B = X – A, rồi kiểm tra xem trong set có B hay không?
  • Cách này chỉ phải loop 1 lần, nên time complexity là O(n).
  • Tuy vậy, ta phải cần thêm bộ nhớ để lưu các phần tử này vào 1 set, nên space complexity sẽ là O(n) luôn.

Nói túm lại, cách 2 sẽ chạy nhanh hơn cách 1, nhưng cần tốn nhiều bộ nhớ hơn. Các bạn có thể xem giải thích và code mẫu ở clip dưới nhé.

Tại sao lại để ra nhiều thuật toán/cấu trúc dữ liệu quá vậy??

Có bao giờ bạn thắc mắc “Tại sao lại đẻ ra lắm cấu trúc dữ liệu, lắm thuật toán vậy” chưa?

Đọc tới phần này, chắc bạn đã đoán ra rồi đấy! Mỗi thuật toán sẽ có time/space complexity khác nhau, giải quyết vấn đề khác nhau. Với 1 vấn đề nào đó, dùng thuật toán A, cấu trúc dữ liệu A thì sẽ nhanh hơn, đỡ tốn tài nguyên hơn so với dùng thuật toán B, cấu trúc dữ liệu B.

Khi đi phỏng vấn thuật toán cũng vậy. Với 1 bài toán đưa ra, các bạn thường sẽ nghĩ ra cách brute-force, chạy chậm nhất nhưng giải quyết được vấn đề.  Sau đó, các bạn sẽ tìm cách optimize, dùng thuật toán/cấu trúc dữ liệu phù hợp để giảm time/space complexity, cho kết quả tối ưu nhất.

Do vậy, việc nắm vững các cấu trúc dữ liệu cơ bản, độ phức tạp của các operation của chúng là rất quan trọng. Chúng sẽ giúp bạn tìm ra cách giải tối ưu của 1 bài toán, khi làm việc cũng như đi phỏng vấn. (Nói đâu xa, kĩ thuật cache ta dùng hàng ngày, là dựa trên CTDL HashTable, tốn thêm bộ nhớ để giảm thời gian tính toán dữ liệu đấy).

 

Tạm kết

Đấy, do bài đã khá dài rồi, nên ở phần này, tụi mình chỉ ôn lại sơ về Big-O Notation, Time/Space Complexity của 1 thuật toán, cấu trúc dữ liệu thôi!

Ở 2 phần sau, mình sẽ giới thiệu kĩ hơn về 8 cấu trúc dữ liệu cơ bản, chúng được sử dụng trong trường hợp nào, một số bài toán phổ biến… để mọi người cùng luyện tập nhé.

Note: Môn thuật toán trong trường Đại Học sẽ dạy kĩ hơn 1 số biểu thức khác như Big-Omega, Big Theta, Small O,… Tuy nhiên, đi làm vài năm mình … chưa từng dùng tới chúng bao giờ nên mình bỏ qua luôn.

Bài viết gốc được đăng tải tại toidicodedao

Có thể bạn quan tâm:

• Tái cấu trúc mã nguồn: Trừu tượng hóa
• Design pattern là gì? Tại sao nên sử dụng Design pattern?

• Nginx và Apache là gì? So sánh Nginx và Apache

Tham khảo thêm các vị trí tuyển dụng ngành IT tại Topdev