Độ phức tạp thuật toán¶

Đặt vấn đề¶

Giả sử mảng gồm 100 phần tử đã sắp xếp tăng dần.

Khi cần kiểm tra xem giá trị nào đó có tồn tại trong mảng hay không, ta nên sử dụng thuật toán tìm kiếm tuần tự hay tìm kiếm nhị phân? Căn cứ vào đâu mà ta cho rằng thuật toán này nhanh hơn thuật toán kia?

Một cách khái quát, khi nhiều thuật toán giải quyết cùng một bài toán, thì thuật toán nào tốt hơn?

Khái niệm¶

Ta luôn muốn chương trình của mình thực thi một thuật toán tốt, theo nghĩa chạy nhanh và chiếm ít bộ nhớ. Có nhiều yếu tố dùng để đánh giá thuật toán tốt hay chưa tốt. Một trong số đó có tên gọi là độ phức tạp của thuật toán.

Theo đó, độ phức tạp thuật toán được phân thành hai loại: độ phức tạp không gian và độ phức tạp thời gian, ứng với hai dạng tài nguyên chính là bộ nhớ và thời gian.

• Độ phức tạp không gian:

  Dùng để xác định dung lượng bộ nhớ cần thiết để thực hiện thuật toán dựa trên kích thước dữ liệu đầu vào.

• Độ phức tạp thời gian:

  Dùng để xác định thời gian thực hiện thuật toán dựa trên kích thước dữ liệu đầu vào.

Cũng có tài liệu nêu rằng, độ phức tạp của thuật toán là độ đo đánh giá hiệu quả của thuật toán, chứ không phải cách thức đo.

Với sự phát triển của phần cứng ngày nay, các máy tính thường có đủ bộ nhớ để chạy chương trình. Do đó, độ phức tạp không gian có thể ít được đề cập hơn so với độ phức tạp thời gian. Và bài này chỉ trình bày về độ phức tạp thời gian của thuật toán, từ nay gọi tắt là độ phức tạp thuật toán.

Ý tưởng xác định độ phức tạp¶

Thời gian để thực hiện một chương trình được tính theo đơn vị giây (hoặc milli-giây), phụ thuộc vào nhiều yếu tố khác nhau như ngôn ngữ lập trình, trình biên dịch, hệ điều hành, tốc độ CPU, v.v... Vì thế, khi đánh giá thuật toán của chương trình, ta không dựa vào thời gian thực, mà cần một đơn vị tính khác, độc lập với những yếu tố trên. Cụ thể hơn, thuật toán cần được đánh giá trên cơ sở là bản thân thuật toán và dữ liệu đầu vào.

Theo ý tưởng này, độ phức tạp thời gian được xác định bằng cách ước lượng số phép toán tích cực cần thực hiện.

1
2
3
4
5

for i in range(n):
    if i % 2 == 0:
        S = S + i
    else:
        P = P * i

1
2
3
4
5

for i in range(n):
    if i % 2 == 0:
        S = S + i
    else:
        P = P * i

Phép toán tích cực bao gồm các phép toán sau:

• Phép so sánh
• Phép gán
• Phép toán số học

Big O¶

Ký hiệu Big O¶

Có ba loại trường hợp khác nhau khi thực hiện thuật toán:

• Trường hợp tốt nhất
• Trường hợp trung bình
• Trường hợp xấu nhất¹

Mỗi trường hợp có một ký hiệu riêng. Trong đó, ký hiệu \(O\), đọc là Big-Oh, có thể xem là phổ biến nhất và thường áp dụng cho trường hợp xấu nhất.

Cách xác định Big O¶

Gọi \(p\) là thời gian thực hiện một phép toán tích cực,
  \(n\) là kích thước của dữ liệu đầu vào,
  \(c(n)\) là hàm số theo \(n\) cho biết số lần thực hiện phép toán tích cực,

thì thời gian thực hiện thuật toán được định nghĩa là:

Ví dụ 1:
Áp dụng cho đoạn mã ở câu hỏi 2:

Giả sử mỗi phép toán tích cực được thực hiện trong một đơn vị thời gian, nghĩa là \(p = 1\);
  và phép toán tích cực được thực hiện \(c(n) = n\) lần.

Như vậy, thời gian thực hiện đoạn mã là: \(T(n) = p . c(n) = 1 . n = n\)

Ví dụ 2:
Cho đoạn mã:

1
2
3

for i in range(n):
    for j in range(n):
        S = S + a[i][j]

Phép toán tích cực trong đoạn mã này là phép cộng dồn cho biến S.

Vì số lần lặp của for i là \(n\) lần và số lần lặp của for j là \(n\) lần, nên phép toán tích cực được thực hiện \(c(n) = n^2\) lần.

Như vậy, thời gian thực hiện đoạn mã là \(T(n) = p . c(n) = 1 . n^2 = n^2\)

Theo đó, Big O của các đoạn mã trên như sau:

• Trong ví dụ 1, vì \(T(n) = n\) nên \(g(n) = O(n)\)
• Trong ví dụ 2, vì \(T(n) = n^2\) nên \(g(n) = O(n^2)\)

Ý nghĩa của Big O¶

Khi phân tích độ phức tạp, ta thường tập trung vào trường hợp xấu nhất, là trường hợp cho thấy được giới hạn cận trên của thuật toán. Ký hiệu Big O cũng thường được sử dụng để chỉ trường hợp xấu nhất này.

Do đó, Big O được dùng để khái quát độ phức tạp của các thuật toán. Dựa vào Big O, ta có thể phân loại các thuật toán khi kích thước dữ liệu vào là như nhau. Nói cách khác,

Một số Big O phổ biến¶

Bảng 1. Một số Big O phổ biến và tên gọi của chúng.

Biểu đồ dưới đây biểu diễn các Big O trên, trừ \(O(n^p)\) nhằm tránh bị rối. Trong đó, các Big O được minh họa từ màu xanh, nghĩa là thuật toán chạy nhanh, chuyển dần cho đến màu đỏ, nghĩa là chạy rất chậm. Cũng xin lưu ý, biểu đồ chỉ là phác thảo mang tính minh họa, giúp người học dễ hình dung về các độ phức tạp, chứ không chính xác một cách chi tiết.

Quy tắc xác định độ phức tạp¶

Việc xác định độ phức tạp của một thuật toán bất kỳ là tương đối... phức tạp (!!!). Tuy nhiên, ta có thể áp dụng những quy tắc sau đây để tính Big O.

Quy tắc hằng số¶

1. Độ phức tạp của mỗi câu lệnh gán, đọc và ghi là \(O(1)\). Đây là độ phức tạp hằng số và không phụ thuộc dữ liệu đầu vào.

   Câu hỏi 5

   Dòng lệnh x = 5 có độ phức tạp là gì?

   Lời giải của bạn:
   O(1)
   Submit

   Đáp án

   x = 5 là lệnh gán, độ phức tạp là \(O(1)\).

2. \(O(c.f(n)) = O(f(n))\), với \(c\) là hằng số. Nói cách khác, ta có thể bỏ đi hằng số \(c\).

   Hệ quả là, khi có nhiều lệnh gán, thì độ phức tạp vẫn được tính là \(O(1)\).

   Câu hỏi 6

   Đoạn mã hoán vị hai biến a và b sau có độ phức tạp là?

   1 2 3

   t = a a = b b = t

   Lời giải của bạn:
   O(1)
   Submit

   Đáp án

   Độ phức tạp của đoạn mã trên là \(3.O(1) = O(1)\).

Quy tắc cộng¶

1. Đối với thuật toán có một vòng lặp, độ phức tạp được tính dựa trên số lần lặp.

   Câu hỏi 7

   Đoạn mã tính tổng từ 1 đến n sau có độ phức tạp là gì?

   1 2	for i in range(n): S = S + i

   Lời giải của bạn:
   O(n)
   Submit

   Đáp án

   Dòng lệnh 2 có độ phức tạp là \(O(1)\) và lệnh này được thực hiện \(n\) lần.

   Do đó, độ phức tạp là \(n.O(1) = O(n)\).

2. Đối với thuật toán gồm hai đoạn mã tuần tự F₁ và F₂, nếu F₁ có độ phức tạp \(O(f_1(n))\) và F₂ có độ phức tạp \(O(f_2(n))\) thì độ phức tạp của cả thuật toán được xác định bằng đoạn mã có độ phức tạp lớn hơn.

   \[ O(f_1(n)) + O(f_2(n)) = O(max(f_1(n), f_2(n))) \]

   Theo đó, quy tắc này còn được gọi là quy tắc lấy max.

   Câu hỏi 8

   Đoạn mã tính tổng các số chẵn và tổng các số lẻ từ 0 đến n sau có độ phức tạp là gì?

   1 2 3 4 5 6 7 8

   n = 10 sum_even, sum_odd = 0, 0 for i in range(0, n, 2): # Đoạn mã F1 gồm dòng lệnh 4 và 5 sum_even = tong_even + i for i in range(1, n, 2): # Đoạn mã F2 gồm dòng lệnh 7 và 8 sum_odd = sum_odd + i

   Lời giải của bạn:
   O(n)
   Submit

   Đáp án

   Vòng lặp F₁ có \(\frac{n}{2}\) lần lặp, nên độ phức tạp là \(O(n)\). (Do hệ số \(\frac{1}{2}\) trong \(\frac{n}{2}\) được lược bỏ).

   Tương tự, vòng lặp F₂ có \(\frac{n}{2}\) lần lặp, nên độ phức tạp là \(O(n)\).

   Thuật toán này có hai vòng lặp tuần tự F₁ và F₂ nên có độ phức tạp là \(max(O(n), O(n)) = O(n)\).

3. Đối với cấu trúc điều kiện if có dạng

   if điều_kiện:
       khối_lệnh_1
   else:
       khối_lệnh_2
   

   vì độ phức tạp của câu lệnh kiểm tra điều_kiện thường là \(O(1)\) nên độ phức tạp sẽ là độ phức tạp lớn nhất của khối_lệnh_1 hoặc khối_lệnh_2.

   Câu hỏi 9

   Đoạn mã tính tổng dương và tổng âm theo điều kiện của x sau có độ phức tạp là gì?

   1 2 3 4

   if x > 0: sum_positive = sum_positive + x else: sum_negative = sum_negative + x

   Lời giải của bạn:
   O(1)
   Submit

   Đáp án

   Dòng lệnh 2 và 4 đều có độ phức tạp là \(O(1)\), nên độ phức tạp của thuật toán này là \(O(1)\).

Quy tắc nhân¶

Đối với thuật toán gồm hai cấu trúc lặp lồng nhau F₁ và F₂, nếu F₁ có độ phức tạp \(O(f_1(n))\) và F₂ có độ phức tạp \(O(f_2(n))\) thì độ phức tạp của thuật toán được xác định bằng độ phức tạp của tích \(f_1\) và \(f_2\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def print_prime_numbers(n):
    for i in range(2, n):      # Vòng lặp F1
        prime = True

        for j in range(2, i):  # Vòng lặp F2
            if i % j == 0:
                prime = False

        if prime == True:
            print(i)

Độ phức tạp của những thuật toán tìm kiếm và sắp xếp¶

Thuật toán tìm kiếm tuần tự¶

1
2
3
4
5
6

def linear_search(A, k):
    for i in range(len(A)):
        if A[i] == k:
            return i

    return -1

Thuật toán tìm kiếm nhị phân¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def binary_search(A, k):
    left = 0
    right = len(A) - 1

    while left <= right:
        mid = (left + right) // 2

        if A[mid] == k:
            return mid
        elif A[mid] < k:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Thuật toán sắp xếp nổi bọt¶

1
2
3
4
5
6
7

def bubble_sort(A):
    n = len(A)

    for i in range(n - 1):
        for j in range(n - 1 - i):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]

Sơ đồ tóm tắt nội dung¶

Some English words¶