I. Lý thuyết trọng tâm

1. Đánh giá thời gian thực hiện chương trình

Thay vì phải cài đặt và chạy chương trình trên máy tính, ta có thể ước lượng thời gian chạy bằng cách đếm tổng số phép tính đơn và lệnh đơn trong chương trình. Cách tính này tuy không chính xác tuyệt đối so với thời gian thực, nhưng đủ để so sánh các thuật toán với nhau một cách đáng tin cậy.

1.1. Nguyên tắc tính thời gian

Khi đánh giá thời gian, ta quy ước mọi phép toán đơn và lệnh đơn đều tốn 1 đơn vị thời gian như nhau. Cụ thể:

1.2. Ví dụ minh hoạ: Hai chương trình

Xét hai chương trình sau:

Chương trình 1 (một vòng lặp):

n = 100          # 1 đơn vị
C = 0            # 1 đơn vị
for k in range(n):   # lặp n lần
    C = C + 1        # 1 đơn vị mỗi lần → tổng n đơn vị
print(C)         # 1 đơn vị

Tổng thời gian: T₁(n) = 1 + 1 + n + 1 = n + 3 đơn vị.

Chương trình 2 (hai vòng lặp lồng nhau):

n = 100          # 1 đơn vị
C = 0            # 1 đơn vị
for i in range(n):       # lặp n lần
    for j in range(n):   # mỗi lần lặp tiếp n lần → tổng n × n = n² lần
        C = C + 1        # 1 đơn vị mỗi lần → tổng n² đơn vị
print(C)         # 1 đơn vị

Tổng thời gian: T₂(n) = 1 + 1 + n² + 1 = n² + 3 đơn vị.

So sánh: Với n = 100, chương trình 1 cần khoảng 103 đơn vị, trong khi chương trình 2 cần khoảng 10.003 đơn vị – chênh lệch gần 100 lần. Khi n càng lớn, khoảng cách càng tăng mạnh.

1.3. Phép toán tích cực

Trong một chương trình, phép toán được thực hiện nhiều lần nhất và đóng vai trò quyết định đến thời gian chạy được gọi là phép toán tích cực.

• Trong chương trình 1: phép toán tích cực là C = C + 1 tại dòng 4 (thực hiện n lần).
• Trong chương trình 2: phép toán tích cực cũng là C = C + 1 tại dòng 5 (thực hiện n² lần).

Xác định được phép toán tích cực giúp ta nhanh chóng ước lượng thời gian chạy mà không cần đếm chi tiết từng lệnh.

2. Phân tích độ phức tạp thời gian thuật toán

2.1. Khái niệm

Độ phức tạp thời gian thuật toán là khối lượng thời gian cần thiết để thực hiện thuật toán, biểu diễn dưới dạng hàm T(n), trong đó n là kích thước dữ liệu đầu vào. Khi n tăng lên, T(n) cũng tăng nhưng với tốc độ tăng khác nhau tuỳ thuộc vào thuật toán.

Để phân loại và so sánh tốc độ tăng của các hàm thời gian, các nhà khoa học sử dụng kí hiệu O-lớn (big-O notation).

2.2. Định nghĩa kí hiệu O-lớn

Cho f(n) và g(n) là hai hàm có đối số là số tự nhiên. Ta viết f(n) = O(g(n)) và nói “f(n) có bậc O-lớn của g(n)” nếu tồn tại hằng số c > 0 và số tự nhiên n₀ ≥ 1 sao cho với mọi n ≥ n₀:

f(n) ≤ c · g(n)

Nói đơn giản: khi n đủ lớn, f(n) không tăng nhanh hơn một bội số nào đó của g(n).

2.3. Ví dụ tính O-lớn

Ví dụ 1: Chương trình 1 có T₁(n) = n + 3.

Chọn c = 2, n₀ = 3. Khi n ≥ 3: T₁(n) = n + 3 ≤ n + n = 2n = c · n.

Vậy T₁(n) = O(n) – độ phức tạp tuyến tính.

Ví dụ 2: Chương trình 2 có T₂(n) = n² + 3.

Chọn c = 2, n₀ = 2. Khi n ≥ 2: T₂(n) = n² + 3 < n² + n₀² ≤ n² + n² = 2n² = c · n².

Vậy T₂(n) = O(n²) – độ phức tạp bình phương.

2.4. Các bậc độ phức tạp thường gặp

Các thuật toán được phân loại theo các bậc độ phức tạp từ nhanh đến chậm:

3. Các quy tắc thực hành tính độ phức tạp

Để tính nhanh O-lớn mà không cần dùng định nghĩa chặt chẽ, ta áp dụng hai quy tắc sau:

3.1. Quy tắc cộng

O(f(n) + g(n)) = O(max(f(n), g(n)))

Khi hai đoạn chương trình thực hiện nối tiếp nhau, độ phức tạp tổng bằng độ phức tạp của đoạn lớn hơn.

Ví dụ: Nếu đoạn 1 có T = O(n) và đoạn 2 có T = O(n²), thì tổng là O(max(n, n²)) = O(n²).

3.2. Quy tắc nhân

Nhân với hằng số: O(C · f(n)) = O(f(n)), với C là hằng số bất kì.

Hằng số nhân không ảnh hưởng đến bậc của hàm. Ví dụ: O(10n²) = O(n²).

Nhân hai hàm: O(f(n) · g(n)) = O(f(n)) · O(g(n)).

Quy tắc này áp dụng khi có hai vòng lặp lồng nhau. Ví dụ: vòng ngoài O(n), vòng trong O(n) → tổng là O(n) · O(n) = O(n²).

3.3. Ví dụ áp dụng quy tắc

Ví dụ 1: T(n) = 10n² → O(10n²) = O(n²) (quy tắc nhân với hằng số).

Ví dụ 2: T(n) = 3n² + n·log(n).

• Áp dụng quy tắc cộng: O(max(3n², n·log(n))) = O(3n²).
• Áp dụng quy tắc nhân hằng số: O(3n²) = O(n²).

Ví dụ 3: T(n) = 2n(n − 2) + 4 = 2n² − 4n + 4.

• Số hạng bậc cao nhất là 2n² → O(2n²) = O(n²).

Ví dụ 4: T(n) = n³ + 5n − 3.

• Số hạng bậc cao nhất là n³ → O(n³).

Mẹo nhanh: Khi tính O-lớn cho đa thức, chỉ cần lấy số hạng bậc cao nhất rồi bỏ hệ số. Ví dụ: 5n³ + 2n² + 100n + 999 → O(n³).

II. Phương pháp giải các dạng bài tập

Dạng 1: Xác định độ phức tạp cho chương trình có một vòng lặp

Phương pháp: Đếm số lần lặp của vòng for hoặc while, đó chính là số lần thực hiện phép toán tích cực. Nếu vòng lặp chạy n lần → O(n). Nếu mỗi bước nhân đôi biến → O(log n).

Bài 1 (Luyện tập SGK). Xác định độ phức tạp thời gian cho chương trình sau:

n = 1000
S = 0
for i in range(n):
    S = S + i * (i + 1)
print(S)

Lời giải:

Phân tích từng dòng:

• Dòng 1, 2: Lệnh gán → 1 + 1 = 2 đơn vị.
• Dòng 3–4: Vòng for lặp n lần. Mỗi lần thực hiện phép nhân i * (i + 1) (1 đơn vị) và phép cộng S = S + ... (1 đơn vị) → mỗi bước lặp cần 2 đơn vị → tổng 2n đơn vị.
• Dòng 5: Lệnh print → 1 đơn vị.

Tổng: T(n) = 2 + 2n + 1 = 2n + 3.

Phép toán tích cực: S = S + i * (i + 1) (thực hiện n lần).

Áp dụng quy tắc nhân hằng số: O(2n + 3) = O(2n) = O(n) – tuyến tính.

Bài 2 (Luyện tập SGK). Xác định độ phức tạp thời gian cho chương trình sau:

n = 1000
Sum = 0
i = 1
while i < n:
    i = i * 2
    Sum = Sum + i
print(Sum)

Lời giải:

Phân tích vòng while:

• Ban đầu i = 1. Sau mỗi bước lặp, i được nhân đôi: 1 → 2 → 4 → 8 → 16 → … → cho đến khi i ≥ n.
• Hỏi: bao nhiêu bước để i đạt hoặc vượt n? Sau k bước, i = 2ᵏ. Cần 2ᵏ ≥ n, tức k ≥ log₂(n). Vậy vòng while lặp khoảng log₂(n) lần.

Phân tích thời gian:

• Dòng 1, 2, 3: 3 đơn vị.
• Vòng while: log₂(n) bước lặp, mỗi bước cần 2 đơn vị (nhân và cộng) → tổng 2·log₂(n) đơn vị.
• Dòng 7: 1 đơn vị.

Tổng: T(n) = 3 + 2·log₂(n) + 1 = 2·log₂(n) + 4.

Phép toán tích cực: i = i * 2 và Sum = Sum + i (thực hiện log₂(n) lần).

Độ phức tạp: O(2·log₂(n) + 4) = O(log n) – logarit.

Nhận biết nhanh: Khi biến lặp nhân đôi (hoặc chia đôi) mỗi bước → độ phức tạp là O(log n).

Dạng 2: Tính O-lớn cho hàm thời gian

Phương pháp: Xác định số hạng bậc cao nhất trong biểu thức, bỏ hệ số. Hoặc áp dụng quy tắc cộng và nhân.

Bài phụ (câu hỏi trong SGK).

a) T(n) = n³ + n·log(n) + 2n + 1.

Áp dụng quy tắc cộng: O(max(n³, n·log(n), 2n, 1)) = O(n³). Vì n³ tăng nhanh nhất.

→ O(n³).

b) T(n) = 3n⁴ + 2n²·log(n) + 10.

Áp dụng quy tắc cộng: O(max(3n⁴, 2n²·log(n), 10)) = O(3n⁴) = O(n⁴).

→ O(n⁴).

Dạng 3: Xác định độ phức tạp cho thuật toán đã học

Phương pháp: Phân tích cấu trúc vòng lặp trong thuật toán: vòng lặp đơn → O(n), hai vòng lặp lồng nhau mỗi vòng n lần → O(n²).

Bài 3 (Vận dụng SGK). Xác định độ phức tạp thời gian của thuật toán sắp xếp chọn (Selection Sort).

Lời giải:

Xét code thuật toán sắp xếp chọn:

def SelectionSort(A):
    n = len(A)                        # 1 đơn vị
    for i in range(n - 1):            # vòng ngoài: n-1 lần
        iMin = i                      # 1 đơn vị
        for j in range(i + 1, n):     # vòng trong: (n-1-i) lần
            if A[j] < A[iMin]:        # 1 đơn vị (phép so sánh)
                iMin = j              # 1 đơn vị
        A[i], A[iMin] = A[iMin], A[i] # 1 đơn vị

Phân tích vòng lặp trong:

• Khi i = 0: vòng trong chạy n − 1 lần.
• Khi i = 1: vòng trong chạy n − 2 lần.
• …
• Khi i = n − 2: vòng trong chạy 1 lần.

Tổng số lần thực hiện phép so sánh (phép toán tích cực):

(n − 1) + (n − 2) + … + 1 = n(n − 1)/2 = (n² − n)/2

Áp dụng quy tắc: O((n² − n)/2) = O(n²/2) = O(n²) – bình phương.

Vậy thuật toán sắp xếp chọn có độ phức tạp thời gian O(n²).

Ghi nhớ: Cả ba thuật toán sắp xếp đã học (chèn, chọn, nổi bọt) đều có độ phức tạp thời gian O(n²) trong trường hợp xấu nhất.

Dạng 4: Đo thời gian thực tế và so sánh

Bài 4 (Vận dụng SGK). Thiết lập chương trình và tính thời gian chạy thực tế của chương trình 1 và chương trình 2 (Hình 24.2) với các giá trị n khác nhau.

Lời giải:

from time import perf_counter

def chuong_trinh_1(n):
    C = 0
    for k in range(n):
        C = C + 1
    return C

def chuong_trinh_2(n):
    C = 0
    for i in range(n):
        for j in range(n):
            C = C + 1
    return C

# Thử với các giá trị n khác nhau
for n in [100, 1000, 5000, 10000]:
    # Đo chương trình 1
    t1 = perf_counter()
    chuong_trinh_1(n)
    t2 = perf_counter()
    time1 = t2 - t1

    # Đo chương trình 2
    t3 = perf_counter()
    chuong_trinh_2(n)
    t4 = perf_counter()
    time2 = t4 - t3

    print(f"n = {n:>6} | CT1: {time1:.6f}s | CT2: {time2:.6f}s | CT2/CT1: {time2/time1:.1f} lần")

Giải thích: Chương trình đo thời gian chạy của cả hai thuật toán với nhiều giá trị n. Cột CT2/CT1 cho thấy chương trình 2 chậm hơn chương trình 1 bao nhiêu lần. Khi n tăng gấp đôi, thời gian chương trình 1 (O(n)) tăng khoảng gấp đôi, trong khi thời gian chương trình 2 (O(n²)) tăng khoảng gấp bốn. Đây chính là ý nghĩa thực tế của sự khác biệt giữa O(n) và O(n²).

III. Sơ đồ tư duy

                                    ┌─ Phép tính số học: 1 đơn vị
                                    ├─ Phép so sánh, logic: 1 đơn vị
  ┌─ Nguyên tắc tính thời gian ────┼─ Lệnh đơn (gán, in): 1 đơn vị
  │                                 ├─ Vòng lặp: tổng thời gian các bước
  │                                 └─ Lệnh if: thời gian nhánh lớn nhất
  │
  │                                 ┌─ Định nghĩa: f(n) ≤ c·g(n) khi n đủ lớn
  ├─ Kí hiệu O-lớn (big-O) ────────┤
  │                                 └─ Các bậc: O(1) < O(logn) < O(n)
  │                                      < O(nlogn) < O(n²) < O(n³) < O(aⁿ)
  │
  │                                 ┌─ QT cộng: O(f + g) = O(max(f, g))
  ├─ Quy tắc tính nhanh ───────────┤   → hai đoạn nối tiếp: lấy cái lớn hơn
  │                                 └─ QT nhân: O(C·f) = O(f)
  │                                      O(f·g) = O(f)·O(g)
  │                                      → vòng lặp lồng nhau: nhân lại
  │
  └─ Phép toán tích cực ─── Phép toán thực hiện nhiều nhất trong CT
                             → quyết định chính đến thời gian chạy

Thầy Phạm Thành Danh

(Người kiểm duyệt, ra đề)

Chức vụ: Trưởng ban biên soạn môn Tin Học THPT

Trình độ: Cử nhân Sư phạm Tin học, Chứng chỉ hạng II, Chứng chỉ Tin học, Ngoại ngữ B1

Kinh nghiệm: 8+ năm kinh nghiệm tại Trường THPT Thuận Hóa