BÀI 24. ĐÁNH GIÁ ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN

PHẦN I. HỆ THỐNG CÂU HỎI, BÀI TẬP TRONG SGK

KHỞI ĐỘNG

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?

1. ĐÁNH GIÁ THỜI GIAN THỰC HIỆN CHƯƠNG TRÌNH

Hoạt động 1: 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.

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

Câu hỏi 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?

2. PHÂN TÍCH ĐỘ PHỨC TẠP THỜI GIAN CỦA THUẬT TOÁN

Hoạt động 2: 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.

Câu hỏi: Tính độ phức tạp của các hàm thời gian sau:

a) Tính = 2n(n - 2) + 4.

b) Tính = n3 + 5n - 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: Đọ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.

Câu hỏ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ính = n³ + nlogn + 2n + 1.

b) Tính = 3n⁴ + 2n²logn + 10.

LUYỆN TẬP

Luyện tập 1: 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)

Luyện tập 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 + 1

Print (Sum)

VẬN DỤNG

Vận dụng 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.

Vận dụ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 nay.

PHẦN II. 5 PHÚT TRẢ LỜI CÂU HỎI, BÀI TẬP SGK

KHỞI ĐỘNG

Đáp án KD:

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

1.ĐÁNH GIÁ THỜI GIAN THỰC HIỆN CHƯƠNG TRÌNH

Đáp án HD1: 

• Chương trình 1: Thời gian là T1=T1(n)=2+n+1=n+3 (đơn vị thời gian)
• Chương trình 2: Thời gian là T2=T1(n)=2+n²+1=n²+3 (đơn vị thời gian)

Đáp án CH1: 

a) T1=1+n//3=1+1000000//3 đơn vị thời gian

b) T2=1+1+(n//3)=2+1000000//3 đơn vị thời gian.

Đáp án CH2: 

Khẳng định sai vì trong một chương trình có thể có nhiều phép toán tích cực, phụ thuộc vào mục đích và logic của chương trình. 

2. PHÂN TÍCH ĐỘ PHỨC TẠP THỜI GIAN CỦA THUẬT TOÁN

Đáp án HD2: 

• O(1) (độ phức tạp thời gian hằng số).
• O(log n) (độ phức tạp thời gian logarithmic).
• O(n) (độ phức tạp thời gian tuyến tính).
• O(n^2) (độ phức tạp thời gian bậc hai)
• O(n^k) (độ phức tạp thời gian bậc k).

Đáp án CH: 

a) T(n) = 2n(n - 2) + 4 = 2n² - 4n + 4 = O(n²)

b) T(n) = n³ + 5n – 3 = O(n³)

3. MỘT SỐ QUY TẮC THỰC HÀNH TÍNH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN

Đáp án HD3: 

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

QT2. Quy tắc nhân:

• Với hằng số: O(C.f(n))=O(f(n))
• Với hàm số: O(f(n).g(n))=O(f(n)).O(g(n))

Đáp án CH: 

a) T(n) = O(n³).

b) T(n) = O(n⁴).

LUYỆN TẬP

Đáp án LT1: 

Vòng for: Vòng lặp này chạy từ 0 đến n-1, với n là 1.000. Vậy số lần lặp là n. Các phép toán trong vòng lặp:

• Phép gán s = s + i*(i+1): Đây là phép gán giá trị vào biến s, có độ phức tạp là O(1).
• Phép toán i*(i+1): Đây là phép nhân và cộng, có độ phức tạp là O(1).

Vậy tổng độ phức tạp thời gian của chương trình là O(n), hay O(1.000)

Đáp án LT2: 

Vòng while: Vòng lặp này chạy cho đến khi i ³ n, và giá trị ban đầu của i là 1. Số lần lặp là log2(n). Các phép toán trong vòng lặp:

- Phép gán i = i * 2: Đây là phép nhân, có độ phức tạp là O(1).

- Phép gán sum = sum + 1: Đây là phép gán giá trị vào biến sum, có độ phức tạp là O(1).

Vậy tổng độ phức tạp thời gian của chương trình là O(log n), hay O(log2(1000)) ≈ O(10)

VẬN DỤNG

Đáp án VD1:

• Số lần so sánh giữa các phần tử là cố định.
• Số lần hoán đổi giữa các phần tử có thể đạt đến tối đa n-1 lần, với n là số phần tử trong mảng hoặc danh sách.

Vậy độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n^2), hay n(n-1)/2 lần so sánh và tối đa n-1 lần hoán đổi giữa các phần tử.

Đáp án VD2:

• Chương trình 1:

from collections import Counter

import time

n = 1000

c = 0

# Ghi lại thời điểm bắt đầu

start_time = time.time()

for k in range(n):

  c = c + 1

# Ghi lại thời điểm kết thúc

end_time = time.time()

# Tính thời gian hoàn thành

elapsed_time = end_time - start_time

# Sử dụng hàm Counter để đếm số lần lặp

counter = Counter(range(n))

# In số lần lặp

print("Số lần lặp: {}".format(counter))

# In thời gian thực thi

print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))

• Chương trình 2:

import time

n = 1000

c = 0

# Ghi lại thời điểm bắt đầu

start_time = time.perf_counter()

for k in range(n):

 for j in range(n):

  c = c + 1

# Ghi lại thời điểm kết thúc

end_time = time.perf_counter()

# Tính thời gian hoàn thành

elapsed_time = end_time - start_time

# In số lần lặp

print("Số lần lặp: {}".format(c))

# In thời gian thực thi

print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))

→ Sự khác biệt: Độ phức tạp thời gian của chương trình 1 là O(1), còn độ phức tạp thời gian của chương trình 2 là O(n2).