Time Complexity — Độ Phức Tạp Của Thuật Toán | TÙNG'S BLOG

Trong lập trình, để giải quyết vấn đề nào đó thì chúng ta cần sử dụng các phép tính toán (độ phức tạp thời gian) và vùng nhớ để lưu trữ (độ phức tạp không gian). Để đánh giá giải thuật này là hiệu quả hơn giải thuật khác ta cần phải đánh giá dựa trên cùng một tập dữ liệu và với kích thước dữ liệu là lớn (vì với tập dữ liệu nhỏ thì sẽ rất khó để đánh giá, vì tốc độ xử lý của máy tính là rất lớn).

1. Các phương pháp tính TM

• Big O (O)
• Big Omega (Ω)
• Big Theta (Θ)

Trong phạm vi bài viết này sẽ nói về Big O (O), đây là phương pháp được sử dụng phổ biến nhất. BigO đánh giá dựa vào thời gian chạy lớn nhất của một giải thuật trên các dữ liệu cùng cỡ.

Ví dụ: Giải thuật tìm kiếm tuyến tính trong trường hợp tốt nhất chỉ cần thực hiện 1 phép tính, trường hợp xấu nhất là n phép tính và trường hợp trung bình là n/2 phép tính (với n là số lượng phần tử). Thì với BigO, độ phức tạp của giải thuật tìm kiếm tuyến tính là O(n).

Một số chỉ số độ phức tạp phổ biến theo mức độ tăng dần:

• Constant time: O(1) số phép tính là hằng số, không phụ thuộc vào dữ liệu đầu vào. vd: a + b
• Logarithmic time: O(logn) số phép tính (thời gian thực hiện) tăng theo kích thước dữ liệu theo hàm logarit. vd: tìm kiếm nhị phân
• Linear time: O(n) số phép tính phụ thuộc vào dữ liệu đầu vào theo 1 biến. vd: tìm kiếm tuyến tính
• Log-linear time: O(nlogn) tổng hợp của n và logn (lồng nhau). vd: Heap sort, Merge sort
• Polynimial time: O(n^c) các vòng lặp lồng nhau
• Exponential time: O(c^n)  bài toán tìm số fibonacci thứ n
• Factorial time: O(n!)  bài toán TSP

2. Các quy tắc tính TM

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

Đơn giản là ta bỏ hằng số đi.

Ví dụ: O(2n + 3n² + 10000) = O(n + n²)

2.2. Quy tắc lấy MAX

Ta lấy độ phức tạp lớn hơn.

Ví dụ: O(n + n²) = O(n²)

2.3. Quy tắc cộng

Ta lấy tổng

Ví dụ: O( n² + m³) (n và m phải khác nhau)

2.4. Quy tắc nhân

Ta lấy tích.

Ví dụ: O(n) * O(logn) = O(nlogn)

2.5. Quy tắc tổng quát để phân tích một chương trình

• Thời gian thực hiện của mỗi lệnh gán, READ, WRITE là O(1).
• Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng qui tắc cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh.
• Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O(1).
• Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp.

2.6. Ví dụ

for (i = 0; i < n; i++) => O(n)

for (i = 0; i < n; i=i+2) => O(n/2) = O(n)

for (i = n; i > 1; i–) => O(n)

for (i = 1; i < n; i=i*2) => O(log2b)

for (i = 1; i < n; i=i*3) => O(log3b)

for (i = n; i > 1; i=i/2) => O(log2b)

3. Tham khảo

Big-O Complexity Chart

8 time complexities that every programmer should know