Phân tích độ phức tạp giải thuật

Table of Contents

1. Độ phức tạp là gì?

Khi lập trình ra một giải pháp nào đó, ở mức độ cơ bản nhất, ta muốn đánh giá xem những dòng code có phải là tốt nhất hay chưa, nếu chưa tốt thì đang nằm ở level nào? Để làm được như vậy, ta cần có một đơn vị đo đạc được, cũng như một phương pháp để giúp xác định được nó.

Và đó là lý do độ phức tạp của giải thuật ra đời, khi nhắc đến nó ta thường nghe đến 2 yếu tố chính:

• Yếu tố về mặt thời gian: được đo đạc bằng việc đếm số lượng "key-operations" -  các thao tác chính.
• Yếu tố về mặt không gian lưu trữ: được đo đạc bằng việc đếm số lượng bộ nhớ "tối đa" cần thiết để chạy giải thuật.

Đơn vị chính dùng để đo đạc 2 yếu tố trên là "Big-O Notation"

2. Đơn vị Big-O

Có nhiều cách để định nghĩa BigO, bao gồm công thức toán và một vài lý thuyết đơn thuần, tuy nhiên để đơn giản hoá nó - mà thực tế thì cũng không cần phải đi qua sâu vào nó, BigO sẽ được định nghĩa như sau:

• Là một công cụ toán học trong khoa học máy tính để mô tả giới hạn trên (trường hợp tệ nhất) về tốc độ tăng trưởng của 2 yếu tố đã nêu trên (thời gian thực thi hoặc bộ nhớ sử dụng) của thuật toán khi kích thước đầu vào (n) tăng lên.
• Mục đích chính là giúp so sánh hiệu suất của các thuật toán một cách trừu tượng. Nó sẽ chỉ tập trung vào sự thay đổi tỷ lệ của hiệu suất khi n tiến đến vô cùng, bỏ qua các hằng số và các thành phần bậc thấp hơn (sẽ mô tả kỹ hơn ở các phần sau), chỉ giữ lại thành phần tăng trưởng nhanh nhất.

Các độ phức tạp phổ biến:

• O(1) (Hằng số): Thời gian không đổi, không phụ thuộc kích thước đầu vào (ví dụ: truy cập một phần tử trong mảng)
• O(log n) (Logarit): Thời gian tăng rất chậm khi đầu vào tăng (ví dụ: tìm kiếm nhị phân)
• O(n) (Tuyến tính): Thời gian tăng tuyến tính với đầu vào (ví dụ: duyệt qua danh sách)
• O(nlog n): Thời gian tăng nhanh hơn tuyến tính (ví dụ: một số thuật toán sắp xếp như Merge Sort)
• O(n^2) (Bậc hai): Thời gian tăng theo bình phương đầu vào (ví dụ: sắp xếp nổi bọt (bubble sort), vòng lặp lồng nhau).

Tham khảo thêm tại: BigO Cheat Sheet

3. Các quy tắc xác định

Sẽ có rất nhiều quy tắc khác nhau để xác định được BigO cuối cùng, tuy nhiên mình sẽ liệt kê những quy tắc cơ bản nhất bắt buộc cần phải nằm lòng. Và các quy tắc ở phía dưới thường sẽ được áp dụng chung với nhau để ra được kết quả cuối cùng không thể rút gọn được nữa.

3.1. Quy tắc bỏ hằng số

Nếu đoạn chương trình P có thời gian thực hiện O(c1.f(n)) với c1 là một hằng số dương thì có thể coi đoạn chương trình đó có độ phức tạp tính toán là O(f(n)).

Ví dụ: 2 đoạn for chạy không lồng nhau, mỗi đoạn O(n) thì ta có O(2n) = O(n).

3.2. Quy tắc lấy max

Nếu đoạn chương trình P có thời gian thực hiện O(f(n) + g(n)) thì có thể coi đoạn chương trình đó có độ phức tạp tính toán O(max(f(n), g(n))).

Ví dụ: 2 đoạn for lồng nhau O(n^2) và 1 đoạn for chạy độc lập O(n) thì lúc này O(n^2 + n) = O(max(n^2, n)) = O(n^2).

3.3. Quy tắc cộng

Nếu đoạn chương trình P1 có thời gian thực hiện T1(n) =O(f(n)) và đoạn chương trình P2 có

thời gian thực hiện là T2(n) = O(g(n)) thì thời gian thực hiện P1 rồi đến P2 tiếp theo sẽ là:

T1(n) + T2(n) = O(f(n) + g(n))

Ví dụ: 1 đoạn có độ phức tạp là O(nlogn), đoạn khác có độ phức tạp là O(n) thì độ phức tạp sẽ là tổng của chúng O(nlogn + n). Sau đó ta có thể áp dụng quy tắc lấy max để ra được O(nlogn)

3.4. Quy tắc nhân

Nếu đoạn chương trình P có thời gian thực hiện là T(n) = O(f(n)). Khi đó, nếu thực hiện k(n) lần đoạn chương trình P với k(n) = O(g(n)) thì độ phức tạp tính toán sẽ là O(g(n).f(n))

Ví dụ: Hay gặp nhất là các vòng for lồng nhau, ví dụ vòng for 1 có độ phức tạp là O(n), vòng for 2 có độ phức tạp là O(nlogn), vòng for 3 có độ phức tạp là O(n^2) thì độ phức tạp sẽ là O(n.nlogn.n^2) = O(n^4logn)

4. Time-Complexity

Từ yếu tố thời gian và đơn vị đo đạc BigO, ta có: độ phức tạp về mặt thời gian - time-complexity chính là tổng thời gian cần thiết để giải thuật có thể thực thi và trả về kết quả.

 

Và để tính được nó, ta cần xác định 2 thành phần chính của một giải thuật:

• Phần thời gian cố định - không bị thay đổi hay ảnh hưởng bởi các yếu tố khác: Bất kỳ câu lệnh nào chỉ được thực thi một lần đều thuộc phần này. Ví dụ: thao tác nhập xuất, if-else, switch, các phép toán số học, v.v.
• Phần thời gian biến đổi: Bất kỳ lệnh nào được thực thi nhiều hơn một lần, chẳng hạn n lần (với n có thể tiến đến vô cực) đều thuộc phần này. Ví dụ: vòng lặp, đệ quy, v.v.

👉 Độ phức tạp về mặt thời gian - Time Complexity được tính bằng TỔNG của 2 phần thời gian trên.

Ví dụ với giải thuật Linear Search - tìm kiếm tuyến tính quen thuộc, time-complexity sẽ được tính toán như sau:

• Lấy n phần tử của mảng trong biến đầu vào là mảng arr[] và số cần tìm trong biến x => Phần thời gian thực hiện biến đổi (Nhận n đầu vào)
• Bắt đầu từ phần tử ngoài cùng bên trái của mảng arr[] và lần lượt so sánh x với từng phần tử của arr[] => Thời gian biến đổi (Cho đến khi đạt độ dài của mảng là (n) hoặc chỉ số của phần tử có giá trị bằng x được tìm thấy)
• Nếu x bằng với một phần tử, trả về True => Thời gian cố định - không đổi với n là bao nhiêu đi nữa.
• Nếu x không bằng với bất kỳ phần tử nào, trả về False => Thời gian cố định.

Vì vậy độ phức tạp sẽ là áp dụng quy tắc cộng ta được: O(n + n(1 + 1) + 1) = O(3n + 1), áp dụng quy tắc lấy max O(max(3n,1) ta được O(3n), sau cùng áp dụng quy tắc bỏ hằng số ta thu lại được kết quả cuối cùng là: O(n)

5. Space-Complexity

Tương tự ta có độ phức tạp về mặt không gian - space-complexity - đại diện cho tổng số lượng không gian lưu trữ cần thiết để  lưu trữ các biến và lấy kết quả. Điều này có thể áp dụng cho dữ liệu đầu vào, các thao tác tạm thời hoặc dữ liệu đầu ra.

Và cũng tương tự, ta cần xác định được 2 thành phần giống như time-complexity:

• Phần cố định: đề cập đến không gian mà thuật toán yêu cầu. Ví dụ: biến đầu vào, biến đầu ra, kích thước chương trình, v.v.
• Phần biến đổi: không gian có thể khác nhau tùy thuộc vào cách triển khai thuật toán. Ví dụ: biến tạm thời, cấp phát bộ nhớ động, không gian ngăn xếp đệ quy, v.v.

👉 Độ phức tạp về mặt không gian - Space Complexity được tính bằng TỔNG của 2 phần trên.

Dùng lại ví dụ ở trên, ta thấy arr[] chính là phần biến đổi và x là phần cố định. Độ phức tạp thời gian lúc này sẽ là O(1 + n) = O(n) với n là số lượng các phần tử.

© hieulm2k | Buy me a coffee