I. Ôn tập kiến thức nền

Bài thực hành này giúp rèn luyện kỹ năng phân tích độ phức tạp thời gian cho các thuật toán đã học. Trước khi thực hành, cần nhớ lại các quy tắc cốt lõi từ Bài 24:

Nguyên tắc đếm thời gian: Mỗi phép toán đơn (cộng, trừ, nhân, chia, so sánh, gán,…) tốn 1 đơn vị thời gian. Vòng lặp tính bằng tổng thời gian các bước lặp.

Kí hiệu O-lớn: $f(n) = O(g(n))$ nếu tồn tại hằng số $c > 0$ và $n_0 \geq 1$ sao cho $f(n) \leq c \cdot g(n)$ với mọi $n \geq n_0$.

Quy tắc cộng: $O(f(n) + g(n)) = O(\max(f(n), g(n)))$ – dùng khi hai đoạn code nối tiếp nhau.

Quy tắc nhân: $O(C \cdot f(n)) = O(f(n))$ – bỏ hằng số. $O(f(n) \cdot g(n)) = O(f(n)) \cdot O(g(n))$ – dùng cho vòng lặp lồng nhau.

Phương pháp chung: Phân tích theo 2 bước:

• Bước 1: Đếm số phép tính cơ bản → tính hàm thời gian $T(n)$.
• Bước 2: Áp dụng quy tắc O-lớn → xác định bậc độ phức tạp.

Công thức hay dùng: Tổng cấp số cộng từ 1 đến $m$:

$$1 + 2 + 3 + \ldots + m = \frac{m(m+1)}{2}$$

II. Hướng dẫn thực hành

Nhiệm vụ 1: Độ phức tạp của tìm kiếm tuần tự

Chương trình cần phân tích

def LinearSearch(A, K):
    for i in range(len(A)):    # dòng 2
        if A[i] == K:          # dòng 3
            return i           # dòng 4
    return -1                  # dòng 5

Bước 1: Phân tích thời gian tính toán

Gọi $n$ = len(A) là kích thước mảng đầu vào, $T(n)$ là thời gian thực hiện thuật toán.

Chương trình duyệt mảng bằng vòng for (dòng 2). Mỗi bước lặp thực hiện phép so sánh A[i] == K (dòng 3) tốn 1 đơn vị. Nếu tìm thấy, chương trình trả về i và kết thúc ngay (dòng 4). Nếu duyệt hết mà không tìm thấy, chương trình trả về −1 (dòng 5).

Phân tích trường hợp xấu nhất (worst case): phần tử cần tìm nằm ở vị trí cuối cùng hoặc không có trong mảng → vòng lặp chạy đủ $n$ bước.

• Vòng lặp dòng 2: $n$ bước lặp, mỗi bước thực hiện 1 phép so sánh (dòng 3) → tổng $n$ đơn vị.
• Lệnh return (dòng 4 hoặc 5): thực hiện đúng 1 lần → 1 đơn vị.

Tổng thời gian trường hợp xấu nhất:

$$T(n) = n + 1$$

Bước 2: Xác định O-lớn

Áp dụng quy tắc cộng:

$$T(n) = n + 1 = O(n + 1) = O(\max(n, 1)) = O(n)$$

Kết luận: Thuật toán tìm kiếm tuần tự có độ phức tạp $O(n)$ – tuyến tính.

Ý nghĩa: Nếu mảng có 1 triệu phần tử, trong trường hợp xấu nhất, thuật toán cần khoảng 1 triệu phép tính.

Nhiệm vụ 2: Độ phức tạp của sắp xếp chọn

Chương trình cần phân tích

def SelectionSort(A):
    n = len(A)                         # dòng 2
    for i in range(n - 1):             # dòng 3
        iMin = i                       # dòng 4
        for j in range(i + 1, n):      # dòng 5
            if A[j] < A[iMin]:         # dòng 6
                iMin = j               # dòng 7
        A[i], A[iMin] = A[iMin], A[i]  # dòng 8

Bước 1: Phân tích thời gian tính toán

Gọi $n$ = len(A), $T(n)$ là thời gian chạy thuật toán.

Dòng 2: Lệnh gán → 1 đơn vị.

Dòng 3: Vòng lặp ngoài – biến i chạy từ 0 đến $n – 2$ → có $n – 1$ bước lặp. Tại mỗi bước lặp $i$, chương trình thực hiện:

• Dòng 4: Lệnh gán iMin = i → 1 đơn vị.
• Dòng 5: Vòng lặp trong – biến j chạy từ $i + 1$ đến $n – 1$ → có $n – i – 1$ bước lặp.
  • Dòng 6: Phép so sánh A[j] < A[iMin] → 1 đơn vị.
  • Dòng 7: Lệnh gán iMin = j (nếu điều kiện đúng) → tối đa 1 đơn vị.
  • → Mỗi bước của vòng trong tốn tối đa 2 đơn vị.
• Dòng 8: Lệnh đổi chỗ (cần 3 phép gán) → 3 đơn vị.

Tổng hợp thời gian:

$$T(n) = 1 + \sum_{i=0}^{n-2} \Big(1 + 2(n – i – 1) + 3\Big)$$

Rút gọn phần trong dấu tổng: $1 + 2(n – i – 1) + 3 = 4 + 2(n – i – 1)$

$$T(n) = 1 + \sum_{i=0}^{n-2} \Big(4 + 2(n – i – 1)\Big)$$

$$T(n) = 1 + 4(n – 1) + 2\sum_{i=0}^{n-2}(n – i – 1)$$

Đặt $k = n – i – 1$, khi $i$ chạy từ 0 đến $n – 2$ thì $k$ chạy từ $n – 1$ xuống 1:

$$\sum_{i=0}^{n-2}(n – i – 1) = \sum_{k=1}^{n-1} k = \frac{(n-1) \cdot n}{2}$$

Thay vào:

$$T(n) = 1 + 4(n – 1) + 2 \cdot \frac{n(n-1)}{2}$$

$$T(n) = 1 + 4(n – 1) + n(n – 1)$$

$$T(n) = 1 + 4n – 4 + n^2 – n$$

$$\boxed{T(n) = n^2 + 3n – 3}$$

Bước 2: Xác định O-lớn

Áp dụng quy tắc cộng:

$$T(n) = O(\max(n^2,\ 3n,\ 3)) = O(n^2)$$

Kết luận: Thuật toán sắp xếp chọn có độ phức tạp $O(n^2)$ – bình phương.

Ý nghĩa: Nếu mảng có 10.000 phần tử, thuật toán cần khoảng $10.000^2 = 100.000.000$ (100 triệu) phép tính. Nếu mảng tăng gấp đôi lên 20.000, thời gian tăng gấp bốn.

III. Phương pháp giải bài tập SGK

Bài Luyện tập

Bài 1 (Luyện tập SGK)

Xác định độ phức tạp của thuật toán sắp xếp nổi bọt:

def BubbleSort(A):
    n = len(A)                              # dòng 2
    for i in range(n - 1):                  # dòng 3
        for j in range(n - 1 - i):          # dòng 4
            if A[j] > A[j + 1]:             # dòng 5
                A[j], A[j + 1] = A[j + 1], A[j]  # dòng 6

Lời giải:

Bước 1 – Phân tích thời gian:

Gọi $n$ = len(A), $T(n)$ là thời gian chạy.

• Dòng 2: Lệnh gán → 1 đơn vị.
• Dòng 3: Vòng ngoài – biến i chạy từ 0 đến $n – 2$ → có $n – 1$ bước lặp.
• Dòng 4: Vòng trong – biến j chạy từ 0 đến $n – 2 – i$ → có $n – 1 – i$ bước lặp.
  • Dòng 5: Phép so sánh → 1 đơn vị.
  • Dòng 6: Đổi chỗ (tối đa) → 3 đơn vị.
  • → Mỗi bước của vòng trong tốn tối đa 4 đơn vị.

Tổng thời gian:

$$T(n) = 1 + \sum_{i=0}^{n-2} 4(n – 1 – i)$$

$$T(n) = 1 + 4\sum_{i=0}^{n-2}(n – 1 – i)$$

Đặt $k = n – 1 – i$, khi $i$ chạy từ 0 đến $n – 2$ thì $k$ chạy từ $n – 1$ xuống 1:

$$\sum_{i=0}^{n-2}(n – 1 – i) = \sum_{k=1}^{n-1} k = \frac{(n-1) \cdot n}{2}$$

Thay vào:

$$T(n) = 1 + 4 \cdot \frac{n(n-1)}{2} = 1 + 2n(n-1) = 2n^2 – 2n + 1$$

Bước 2 – Xác định O-lớn:

$$T(n) = 2n^2 – 2n + 1 = O(\max(2n^2, 2n, 1)) = O(2n^2) = O(n^2)$$

Kết luận: Thuật toán sắp xếp nổi bọt có độ phức tạp $O(n^2)$ – bình phương, giống sắp xếp chọn.

Bài 2 (Luyện tập SGK)

Cho biết hàm sau trả về giá trị bao nhiêu? Xác định độ phức tạp thời gian O-lớn.

def Mystery(n):
    r = 0                          # dòng 2
    for i in range(n - 1):         # dòng 3
        for j in range(i + 1, n):  # dòng 4
            for k in range(1, j):  # dòng 5
                r = r + 1          # dòng 6
    return r                       # dòng 7

Lời giải:

Hàm trả về giá trị gì?

Biến r bắt đầu bằng 0, mỗi lần lệnh r = r + 1 được thực hiện thì r tăng thêm 1. Vậy r chính là tổng số lần lệnh dòng 6 được thực hiện – tức là tổng số bước lặp của cả ba vòng for lồng nhau.

Phân tích cấu trúc vòng lặp:

• Vòng ngoài (dòng 3): i chạy từ 0 đến $n – 2$.
• Vòng giữa (dòng 4): j chạy từ $i + 1$ đến $n – 1$.
• Vòng trong (dòng 5): k chạy từ 1 đến $j – 1$ → có $j – 1$ bước lặp.

Tổng số lần thực hiện r = r + 1:

$$r = \sum_{i=0}^{n-2}\ \sum_{j=i+1}^{n-1}\ (j – 1)$$

Đây là biểu thức phức tạp. Ta phân tích bằng cách ước lượng bậc:

• Vòng ngoài: $O(n)$ bước.
• Vòng giữa: mỗi bước cũng tối đa $O(n)$ bước.
• Vòng trong: mỗi bước cũng tối đa $O(n)$ bước.

Ba vòng lặp lồng nhau, mỗi vòng tối đa $n$ bước → tổng số phép tính tối đa cỡ $n \times n \times n$.

Xác định O-lớn:

$$T(n) = O(n^3)$$

Kết luận: Hàm Mystery(n) đếm tổng số bộ ba $(i, j, k)$ thoả mãn điều kiện của ba vòng lặp. Độ phức tạp thời gian là $O(n^3)$ – bậc ba.

Bài Vận dụng

Bài 1 (Vận dụng SGK)

Giả sử rằng mỗi phép tính đơn được thực hiện trong 1 micro giây (1 μs = một phần triệu giây). Hãy xác định giá trị lớn nhất của n trong các thuật toán tìm kiếm tuần tự, sắp xếp chèn và sắp xếp chọn nếu thời gian thực thi các thuật toán là 1 giây, 1 phút và 1 giờ.

Lời giải:

Quy đổi thời gian sang micro giây:

• 1 giây = $10^6\ \mu s$
• 1 phút = $60 \times 10^6 = 6 \times 10^7\ \mu s$
• 1 giờ = $3600 \times 10^6 = 3{,}6 \times 10^9\ \mu s$

Tìm kiếm tuần tự – $O(n)$: Mỗi phép tính tốn $1\ \mu s$, cần $n$ phép tính → thời gian = $n\ \mu s$. Vậy $n$ tối đa bằng số micro giây khả dụng.

Sắp xếp chèn và sắp xếp chọn – $O(n^2)$: Cần khoảng $n^2$ phép tính → thời gian = $n^2\ \mu s$. Vậy $n$ tối đa $= \sqrt{\text{số micro giây khả dụng}}$.

Kết quả:

Cách tính cột sắp xếp ($O(n^2)$):

• 1 giây: $n^2 \leq 10^6$ → $n \leq \sqrt{10^6} = 10^3 = 1.000$.
• 1 phút: $n^2 \leq 6 \times 10^7$ → $n \leq \sqrt{6 \times 10^7} \approx 7.746$.
• 1 giờ: $n^2 \leq 3{,}6 \times 10^9$ → $n \leq \sqrt{3{,}6 \times 10^9} = 60.000$.

Nhận xét: Với thuật toán tuyến tính $O(n)$, ta có thể xử lý hàng tỷ phần tử trong 1 giờ. Nhưng với thuật toán bình phương $O(n^2)$, chỉ xử lý được khoảng 60.000 phần tử trong cùng thời gian. Sự khác biệt về bậc độ phức tạp có ảnh hưởng rất lớn đến khả năng xử lý dữ liệu thực tế.

Bài 2 (Vận dụng SGK)

Cho biết hàm sau thực hiện công việc gì. Xác định độ phức tạp thời gian.

def func(A):
    n = len(A)                          # dòng 2
    for i in range(n - 1):              # dòng 3
        for j in range(i + 1, n):       # dòng 4
            if A[i] > A[j]:             # dòng 5
                A[i], A[j] = A[j], A[i] # dòng 6

Lời giải:

Hàm thực hiện công việc gì?

Quan sát cấu trúc: hai vòng lặp lồng nhau, so sánh A[i] với A[j] (với $j > i$), nếu A[i] > A[j] thì đổi chỗ. Sau khi vòng trong kết thúc với một giá trị i cụ thể, A[i] sẽ chứa phần tử nhỏ nhất trong đoạn từ A[i] đến A[n-1].

Đây thực chất là một biến thể của thuật toán sắp xếp chọn – thay vì tìm chỉ số min rồi đổi chỗ một lần, nó đổi chỗ ngay mỗi khi tìm thấy phần tử nhỏ hơn. Kết quả cuối cùng vẫn là dãy A được sắp xếp tăng dần.

Phân tích độ phức tạp:

• Dòng 2: 1 đơn vị.
• Dòng 3: Vòng ngoài: $n – 1$ bước.
• Dòng 4: Vòng trong: $n – 1 – i$ bước cho mỗi $i$.
  • Dòng 5: So sánh → 1 đơn vị.
  • Dòng 6: Đổi chỗ (tối đa) → 3 đơn vị.
  • → Mỗi bước tối đa 4 đơn vị.

Tổng thời gian (tương tự phân tích Bubble Sort):

$$T(n) = 1 + \sum_{i=0}^{n-2} 4(n – 1 – i) = 1 + 4 \cdot \frac{n(n-1)}{2} = 2n^2 – 2n + 1$$

Xác định O-lớn:

$$T(n) = 2n^2 – 2n + 1 = O(n^2)$$

Kết luận: Hàm func(A) thực hiện sắp xếp mảng A theo thứ tự tăng dần (biến thể của sắp xếp chọn). Độ phức tạp thời gian là $O(n^2)$ – bình phương.

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