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 viết bởi Phạm Huy Hoàng

Có thể bạn quan tâm

Hãy bỏ qua các công nghệ phức tạp một chút, lần này chúng ta hãy cùng ôn lại những kiến thức cơ bản về thuật toán và cấu trúc dữ liệu, nhé?

Bạn đang xem: 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

Mặc dù kiến thức về thuật toán không phổ biến trong công việc lập trình hàng ngày, nhưng nó giúp bạn viết mã tối ưu hơn và xử lý nhanh hơn. Ngoài ra, hiện nay rất nhiều công ty sử dụng thuật toán trong quá trình phỏng vấn.

Có rất nhiều thuật toán và cấu trúc dữ liệu khác nhau, đủ để viết một cuốn sách dày. Tuy nhiên, chúng ta chỉ cần tập trung vào 8 cấu trúc dữ liệu cơ bản này.

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

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

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

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

Có 3 trường hợp phổ biến:

Độ phức tạp O(n): Số lượng thao tác tăng tuyến tính theo số lượng phần tử đầu vào.
Độ phức tạp O(n²): Số lượng thao tác tăng theo bình phương số lượng phần tử đầu vào.
Độ phức tạp lớn hơn sẽ khiến thuật toán chạy chậm hơn khi số lượng phần tử tăng lên.

Ví dụ, trong bài toán tìm đường cho người đưa thư qua nhiều thành phố (traveling salesman problem), sử dụng thuật toán vét cạn có độ phức tạp là O(n!). Điều này có nghĩa là khi số lượng địa điểm tăng lên đến vài ngàn, thì thời gian chạy sẽ rất lâu.

Big-O Notation

Phân biệt time và space complexity

Big O có thể được sử dụng để đo đạc thời gian chạy (số lượng thao tác) và bộ nhớ mà thuật toán sử dụng.

Để phân biệt dễ dàng, chúng ta có:

Time Complexity: Số lượng thao tác phải chạy hoặc thời gian chạy của thuật toán, phụ thuộc vào số lượng phần tử đầu vào.
Space Complexity: Số lượng bộ nhớ bổ sung mà thuật toán sử dụng, phụ thuộc vào số lượng phần tử đầu vào.

Chữ “độ phức tạp” chính là từ “complexity” mà ra.

Ví dụ, giả sử chúng ta có một bài toán đơn giản như tìm hai số trong một mảng có tổng bằng X. Có hai cách để giải quyết:

Cách 1: Sử dụng hai vòng lặp để duyệt qua tất cả các cặp phần tử trong mảng. Cách này không tốn thêm bộ nhớ, nhưng độ phức tạp thời gian là O(n²) vì chúng ta cần chạy hai vòng lặp lồng nhau với n phần tử trong mỗi vòng lặp.
Cách 2: Duyệt qua từng phần tử, lưu các số đã duyệt vào một set. Mỗi khi gặp một số A, ta tính số B = X – A và kiểm tra xem có tồn tại B trong set không? Cách này chỉ cần duyệt qua mảng một lần, vì vậy độ phức tạp thời gian là O(n). Tuy nhiên, ta cần dùng thêm bộ nhớ để lưu các phần tử trong set, vì vậy độ phức tạp không gian là O(n).

Tóm lại, cách 2 sẽ chạy nhanh hơn cách 1, nhưng yêu cầu nhiều bộ nhớ hơn. Bạn có thể xem giải thích và mã nguồn mẫu trong video dưới đây.

Tại sao lại có nhiều thuật toán và cấu trúc dữ liệu?

Bạn có bao giờ tự hỏi “Tại sao lại có nhiều cấu trúc dữ liệu và thuật toán?” chưa?

Đọc đến đây, bạn đã đoán ra câu trả lời rồi đấy! Mỗi thuật toán sẽ có time và space complexity khác nhau, giải quyết các vấn đề khác nhau. Với một vấn đề cụ thể, sử dụng thuật toán và cấu trúc dữ liệu A có thể nhanh hơn và tiết kiệm tài nguyên hơn so với thuật toán và cấu trúc dữ liệu B.

Xem thêm : Phân tích giá trị biên – Kỹ thuật trong kiểm thử hộp đen

Cũng tương tự như khi đi phỏng vấn, khi ta đề cập đến một bài toán, ta thường nghĩ ra cách brute-force đầu tiên, tức là cách chạy chậm nhất nhưng vẫn giải quyết được vấn đề. Sau đó, ta tìm cách tối ưu, sử dụng thuật toán và cấu trúc dữ liệu phù hợp để giảm độ phức tạp thời gian và không gian, cho kết quả tối ưu nhất.

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

Tạm kết

Bài viết đã trở nên khá dài, vì vậy ở phần này, chúng ta chỉ ôn lại một ít về Big-O Notation, Time Complexity và Space Complexity của thuật toán và cấu trúc dữ liệu.

Ở hai phần tiếp theo, tôi sẽ giới thiệu chi tiết hơn về 8 cấu trúc dữ liệu cơ bản, cách sử dụng chúng trong các trường hợp cụ thể và một số bài toán phổ biến để cùng luyện tập.

Note: Môn học thuật toán trong trường Đại học sẽ nói rõ hơn về các biểu thức khác như Big-Omega, Big Theta, Small O. Tuy nhiên, sau nhiều năm làm việc, tôi chưa bao giờ sử dụng chúng, vì vậy tôi đã bỏ qua chúng hoàn toàn.

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

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