Bài viết tổng hợp dưới đây sẽ giúp bạn ôn lại kiến thức về các cấu trúc dữ liệu và thuật toán cơ bản. Dù không phải lúc nào chúng cũng được sử dụng trong việc viết code hàng ngày, nhưng kiến thức này sẽ giúp bạn viết code hiệu quả và xử lý nhanh chóng hơn. Đồng thời, nhiều công ty ngày nay hay phỏng vấn ứng viên với các câu hỏi liên quan đến thuật toán.
Ô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 biểu diễn bằng Big-O Notation. Nó mô tả mối liên hệ giữa số lượng phần tử đầu vào và số lượng phép toán hoặc bộ nhớ mà thuật toán cần sử dụng.
Ví dụ, với thuật toán có độ phức tạp O(n), khi số lượng phần tử đầu vào tăng gấp đôi, số lượng phép toán cũng phải tăng gấp đôi. Tương tự, với độ phức tạp O(n²), khi số lượng phần tử đầu vào tăng gấp đôi, số lượng phép toán tăng gấp 4 lần.
Điều này có nghĩa là thuật toán càng phức tạp, khi số lượng phần tử càng lớn, nó sẽ chạy càng chậm.
Phân biệt time và space complexity
Big-O Notation có thể áp dụng cho cả thời gian chạy và lượng bộ nhớ mà thuật toán sử dụng. Cụ thể:
- Time Complexity: Số lượng phép toán cần chạy – thời gian chạy của thuật toán dựa trên số lượng phần tử đầu vào.
- Space Complexity: Lượng bộ nhớ mà thuật toán sử dụng, cũng dựa trên số lượng phần tử đầu vào.
Cho ví dụ bài toán Two Sum cơ bản: Cho một mảng gồm N số không trùng nhau. Hãy tìm hai số trong mảng có tổng bằng X.
Có hai cách để giải quyết bài toán này:
- Cách 1: Sử dụng hai vòng lặp lồng nhau để duyệt qua từng phần tử trong mảng để lấy các cặp số. 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ới n là số lượng phần tử trong mảng.
- Cách 2: Duyệt từng phần tử, lưu các phần tử đã duyệt vào một set. Mỗi khi gặp một phần tử có giá trị A, ta tính giá trị B = X – A, sau đó kiểm tra xem trong set có giá trị B hay không. Cách này chỉ cần duyệt mảng một lần, vì vậy độ phức tạp thời gian là O(n). Tuy nhiên, cách này sẽ tốn thêm bộ nhớ để lưu các phần tử trong set, nên độ phức tạp bộ nhớ là O(n).
Tóm lại, cách thứ hai sẽ chạy nhanh hơn cách đầu tiên, nhưng tốn nhiều bộ nhớ hơn. Điều này cho thấy việc hiểu rõ các cấu trúc dữ liệu và độ phức tạp của các phép toán là quan trọng. Nó giúp chúng ta tìm ra cách giải quyết tối ưu cho một bài toán khi làm việc hoặc đi phỏng vấn.
Tại sao lại có nhiều thuật toán và cấu trúc dữ liệu?
Có thể bạn đã tự hỏi, “Tại sao lại có nhiều thuật toán và cấu trúc dữ liệu?”.
Mỗi thuật toán và cấu trúc dữ liệu có độ phức tạp thời gian và bộ nhớ khác nhau, và chúng 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 sẽ 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.
Khi tham gia phỏng vấn, chúng ta thường nghĩ ra một giải pháp brute-force, dù chậm nhưng có thể giải quyết được vấn đề. Sau đó, chúng ta sẽ tìm cách tối ưu bằng cách sử dụng thuật toán và cấu trúc dữ liệu để giảm độ phức tạp thời gian và bộ nhớ, mang lại kết quả tối ưu nhất.
Do đó, việc nắm vững các cấu trúc dữ liệu cơ bản và hiểu độ phức tạp của các phép toán là rất quan trọng. Nó sẽ giúp bạn tìm ra cách giải quyết tối ưu cho một bài toán khi làm việc hoặc đi phỏng vấn.
Dnulib sẽ giới thiệu kĩ hơn về 8 cấu trúc dữ liệu cơ bản trong các bài viết tiếp theo. Hãy truy cập Dnulib để tìm hiểu thêm về chủ đề này và luyện tập kỹ năng của bạn.
