HIỂU ĐƠN GIẢN VỀ ĐỘ PHỨC TẠP THUẬT TOÁN

🔍 Tổng quan

Độ phức tạp thuật toán (Big-O) cho biết thời gian chạy của thuật toán thay đổi như thế nào khi kích thước dữ liệu tăng lên. Dưới đây là các dạng phổ biến kèm ví dụ và bảng so sánh.

1. Độ phức tạp hằng số — O(1)

Thuật toán chạy trong thời gian cố định, không phụ thuộc kích thước dữ liệu.

Ví dụ

x = arr[0]  # Lấy phần tử đầu tiên – luôn mất 1 bước
  

2. Độ phức tạp tuyến tính — O(n)

Thời gian chạy tăng tỉ lệ thuận với số lượng phần tử.

for x in arr:
    print(x)
  

3. Độ phức tạp bình phương — O(n²)

Thường gặp khi có vòng lặp lồng nhau.

for i in range(n):
    for j in range(n):
        print(i, j)
  

4. Độ phức tạp logarit — O(log n)

Xuất hiện trong thuật toán chia đôi dữ liệu (ví dụ: tìm kiếm nhị phân).

while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
        break
    elif arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
  

5. Độ phức tạp n log n — O(n log n)

Thường gặp trong các thuật toán sắp xếp hiệu quả (Merge Sort, Quick Sort trung bình).

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
  

6. Độ phức tạp m × n — O(mn)

Gặp khi dữ liệu có hai chiều độc lập (ví dụ: duyệt ma trận).

for i in range(m):
    for j in range(n):
        print(i, j)
  

Bảng so sánh tốc độ tăng

So sánh số bước ước lượng cho các độ phức tạp khác nhau khi n là vài giá trị mẫu:

n	O(1)	O(n)	O(n²)	O(n log n)	O(2ⁿ)
5	1	5	25	~11	32
10	1	10	100	~33	1,024
20	1	20	400	~86	1,048,576

Kết luận:

O(1), O(n), O(n log n) thường chấp nhận được; O(n²) sẽ chậm khi n lớn; O(2ⁿ) hầu như không khả thi cho n lớn.