Câu hỏi mở đầu trang 111

Đề bài: Quan sát và ước lượng thời gian thực hiện các đoạn chương trình 1 và 2 trong Hình 24.2. Chương trình nào chạy nhanh hơn? Vì sao?

Chương trình 1:

n = 100
C = 0
for k in range(n):
    C = C + 1
print(C)

Chương trình 2:

n = 100
C = 0
for i in range(n):
    for j in range(n):
        C = C + 1
print(C)

Lời giải:

Chương trình 1 chạy nhanh hơn.

Giải thích:

• Chương trình 1 có một vòng lặp với n bước → thực hiện n phép cộng.
• Chương trình 2 có hai vòng lặp lồng nhau, mỗi vòng n bước → thực hiện n × n = n² phép cộng.
• Với n = 100: Chương trình 1 làm 100 phép, Chương trình 2 làm 10 000 phép → Chương trình 1 nhanh hơn rất nhiều.

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

Hoạt động 1 trang 112

Đề bài: Quan sát và thực hiện đánh giá thời gian chạy của các chương trình 1 và 2 trong Hình 24.2. Từ đó biết và hiểu được cách đánh giá thời gian thực hiện chương trình.

Lời giải:

Chương trình 1 – gọi T₁ là thời gian chạy:

→ $T_1(n) = 2 + n + 1 = n + 3$ đơn vị thời gian.

Chương trình 2 – gọi T₂ là thời gian chạy:

→ $T_2(n) = 2 + n^2 + 1 = n^2 + 3$ đơn vị thời gian.

Kết luận: Chương trình 1 có thời gian bậc n, chương trình 2 có thời gian bậc n². Với n lớn, chương trình 2 chạy chậm hơn rất nhiều.

Câu hỏi củng cố mục 1 trang 113

Đề bài:

1. Các lệnh và đoạn chương trình sau cần chạy trong bao nhiêu đơn vị thời gian?

(a)

n = 1000000
for k in range(n):
    if k%3 == 0:
        print(k)

(b)

n = 1000000
b = 3
for k in range(0, n, b):
    print(k)

Lời giải:

Đoạn (a):

• Dòng 1 (lệnh gán): 1 đơn vị.
• Vòng lặp (dòng 2 – 4) chạy n bước. Mỗi bước có:
  • Kiểm tra điều kiện if: 1 đơn vị.
  • Nhánh của if: theo nguyên tắc 5, tính bằng nhánh lớn nhất → 1 đơn vị (lệnh print).
  • Tổng mỗi bước: 2 đơn vị.
• Vòng lặp: n × 2 = 2n đơn vị.

→ $T_a(n) = 1 + 2n = 2n + 1$ đơn vị.

Với n = 1 000 000: $T_a \approx 2,000,001$ đơn vị.

Đoạn (b):

• Dòng 1, 2 (2 lệnh gán): 2 đơn vị.
• Vòng lặp có bước nhảy b = 3, nên số bước lặp là $\dfrac{n}{b} = \dfrac{n}{3}$.
• Mỗi bước 1 đơn vị (print) → tổng vòng lặp: n/3 đơn vị.

→ $T_b(n) = 2 + \dfrac{n}{3}$ đơn vị.

Với n = 1 000 000: $T_b \approx 333,335$ đơn vị.

So sánh: Đoạn (b) chạy nhanh hơn đoạn (a) khoảng 6 lần, dù cả hai đều có độ phức tạp bậc n.

2. Khẳng định “Trong mọi chương trình chỉ có đúng một phép toán tích cực” là đúng hay sai?

Lời giải:

Khẳng định trên là sai.

Giải thích: Phép toán tích cực là phép toán được thực hiện nhiều nhất trong chương trình. Một chương trình có thể có nhiều phép toán cùng số lần thực hiện lớn nhất, khi đó tất cả đều là phép toán tích cực.

Ví dụ: Trong vòng lặp for i in range(n): S = S + i*(i+1), cả phép cộng, phép nhân đều xuất hiện n lần → đều là phép toán tích cực.

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

Hoạt động 2 trang 113

Đề bài: Cùng trao đổi và tìm hiểu cách phân loại thuật toán dựa trên độ phức tạp thời gian thuật toán.

Lời giải:

Khái niệm độ phức tạp thời gian: là khối lượng thời gian cần thiết để chạy chương trình thể hiện thuật toán, thường biểu diễn bằng hàm số $T(n)$ với n là kích thước dữ liệu đầu vào.

Kí hiệu O-lớn (big-O): dùng để so sánh và phân loại bậc của hàm thời gian $T(n)$ khi n tăng lên vô cùng.

Định nghĩa: Ta viết $f(n) = O(g(n))$ nếu tồn tại hằng số $c > 0$ và số tự nhiên $n_0 \geq 1$ sao cho với mọi $n \geq n_0$: $f(n) \leq c \cdot g(n)$.

Ví dụ:

• Chương trình 1 có $T_1(n) = n + 3$. Chọn $c = 2$, $n_0 = 3$ thì với $n \geq 3$: $T_1(n) = n + 3 \leq n + n = 2n$. Vậy $T_1(n) = O(n)$ – tuyến tính.
• Chương trình 2 có $T_2(n) = n^2 + 3$. Chọn $c = 2$, $n_0 = 2$ thì với $n \geq 2$: $T_2(n) = n^2 + 3 \leq 2n^2$. Vậy $T_2(n) = O(n^2)$ – bình phương.

Một số hàm chuẩn thường gặp: $O(1)$ – hằng số, $O(\log n)$ – logarit, $O(n)$ – tuyến tính, $O(n\log n)$ – tuyến tính logarit, $O(n^2)$ – bình phương, $O(n^k)$ – đa thức, $O(a^n)$ – luỹ thừa, $O(n!)$ – giai thừa.

Câu hỏi củng cố mục 2 trang 114

Đề bài: Tính độ phức tạp của các hàm thời gian sau:

a) $T(n) = 2n(n – 2) + 4$.

b) $T(n) = n^3 + 5n – 3$.

Lời giải:

a) $T(n) = 2n(n – 2) + 4 = 2n^2 – 4n + 4$.

Hạng tử có bậc cao nhất là $2n^2$. Chọn $c = 2$, $n_0 = 1$: với $n \geq 1$ thì $T(n) = 2n^2 – 4n + 4 \leq 2n^2$.

→ $T(n) = O(n^2)$ – bình phương.

b) $T(n) = n^3 + 5n – 3$.

Hạng tử có bậc cao nhất là $n^3$. Chọn $c = 2$, $n_0 = 3$: với $n \geq 3$ thì $5n \leq n^3$ (vì $n^2 \geq 9 > 5$), do đó $T(n) \leq n^3 + n^3 = 2n^3$.

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

3. Một số quy tắc thực hành tính độ phức tạp thời gian thuật toán

Hoạt động 3 trang 114

Đề bài: Đọc, quan sát, thảo luận để biết một số quy tắc đơn giản tính độ phức tạp thời gian thuật toán.

Lời giải:

Có hai quy tắc chính:

QT1 – Quy tắc cộng: $O(f(n) + g(n)) = O(\max(f(n), g(n)))$.

→ Dùng khi hai chương trình chạy nối tiếp nhau – chỉ giữ lại hàm có bậc lớn hơn.

QT2 – Quy tắc nhân:

• Nhân với hằng số: $O(C \cdot f(n)) = O(f(n))$ (bỏ hằng số).
• Nhân với hàm số: $O(f(n) \cdot g(n)) = O(f(n) \cdot g(n))$.

→ Dùng khi tính chương trình có hai vòng lặp lồng nhau.

Ví dụ:

• $T(n) = 10n^2 = O(n^2)$ (bỏ hằng số 10).
• $T(n) = 3n^2 + n\log n = O(\max(3n^2, n\log n)) = O(3n^2) = O(n^2)$.

Câu hỏi củng cố mục 3 trang 114

Đề bài: Áp dụng các quy tắc trên để tính độ phức tạp của các hàm thời gian sau:

a) $T(n) = n^3 + n\log n + 2n + 1$.

b) $T(n) = 3n^4 + 2n^2 \log n + 10$.

Lời giải:

a) $T(n) = n^3 + n\log n + 2n + 1$.

Áp dụng quy tắc cộng, chỉ giữ hạng tử có bậc lớn nhất:

• So sánh: $n^3$ > $n\log n$ > $2n$ > $1$.
• $\max(n^3, n\log n, 2n, 1) = n^3$.

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

b) $T(n) = 3n^4 + 2n^2 \log n + 10$.

• Bỏ hằng số: $3n^4 = O(n^4)$, $2n^2\log n = O(n^2\log n)$.
• So sánh: $n^4 > n^2\log n > 1$.
• $\max(n^4, n^2\log n, 1) = n^4$.

→ $T(n) = O(n^4)$.

Luyện tập

Luyện tập trang 114

Đề bài:

1. Xác định độ phức tạp thời gian tính toán 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:

• Dòng 1, 2 (lệnh gán): 2 đơn vị.
• Vòng lặp (dòng 3, 4) chạy n bước, mỗi bước 1 đơn vị → n đơn vị.
• Dòng 5 (print): 1 đơn vị.

→ $T(n) = 2 + n + 1 = n + 3$.

Áp dụng: $T(n) = O(n)$ – tuyến tính.

2. Xác định độ phức tạp thời gian tính toán 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:

• Dòng 1, 2, 3 (lệnh gán): 3 đơn vị.
• Vòng lặp: biến i bắt đầu bằng 1, sau mỗi bước i nhân đôi (i = 1, 2, 4, 8, …). Số bước lặp bằng số lần nhân đôi cho đến khi $i \geq n$, tức là $\log_2 n$ bước.
• Mỗi bước có 2 lệnh gán → 2 đơn vị. Tổng vòng lặp: $2\log_2 n$ đơn vị.
• Dòng 7 (print): 1 đơn vị.

→ $T(n) = 3 + 2\log_2 n + 1 = 2\log_2 n + 4$.

Áp dụng: $T(n) = O(\log n)$ – logarit.

Vận dụng

Vận dụng trang 114

Đề bài:

1. Xác định độ phức tạp thời gian của thuật toán sắp xếp chọn đã được học trong Bài 21.

Lời giải:

Thuật toán sắp xếp chọn:

def SelectionSort(A):
    n = len(A)
    for i in range(n-1):
        iMin = i
        for j in range(i+1, n):
            if A[j] < A[iMin]:
                iMin = j
        A[i], A[iMin] = A[iMin], A[i]

Phân tích:

• Vòng ngoài i chạy $n – 1$ lần.
• Vòng trong j chạy $n – 1 – i$ lần (số lần giảm dần theo i).
• Phép so sánh A[j] < A[iMin] là phép toán tích cực.
• Tổng số lần so sánh:

$$(n-1) + (n-2) + \ldots + 1 = \dfrac{n(n-1)}{2} = \dfrac{n^2 – n}{2}$$

Áp dụng quy tắc: $T(n) = \dfrac{n^2 – n}{2} = O(n^2)$.

→ Độ phức tạp thời gian của thuật toán sắp xếp chọn là $O(n^2)$ – bình phương.

2. Em hãy thiết lập chương trình và tính thời gian chạy thực tế trên máy tính của các chương trình 1 và 2 ở Hình 24.2 với các giá trị n khác nhau, từ đó thấy được ý nghĩa sự khác biệt độ phức tạp thời gian của hai chương trình này.

Lời giải:

from time import perf_counter

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

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

# Đo thời gian với các giá trị n khác nhau
for n in [100, 1000, 10000]:
    t1 = perf_counter()
    CT1(n)
    t2 = perf_counter()
    print("CT1 với n =", n, ": thời gian =", t2 - t1, "giây")

    t1 = perf_counter()
    CT2(n)
    t2 = perf_counter()
    print("CT2 với n =", n, ": thời gian =", t2 - t1, "giây")

Nhận xét:

• Với n nhỏ, thời gian chạy 2 chương trình chênh lệch không đáng kể.
• Khi n tăng lên, thời gian của CT2 tăng rất nhanh so với CT1:
  • n tăng 10 lần → CT1 chạy chậm gấp khoảng 10 lần, còn CT2 chạy chậm gấp khoảng 100 lần.
• Điều này phù hợp với lý thuyết: CT1 có độ phức tạp $O(n)$, còn CT2 có độ phức tạp $O(n^2)$.

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