Hướng dẫn giải nhanh Tin học 11 định hướng Khoa học máy tính KNTT bài 24: Đánh giá độ phức tạp thời gian thuật toán

MỞ ĐẦU

Câu 1: 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?

Trả lời:

Chương trình 1 

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

Hoạt động 1. Tìm hiểu cách đánh giá thời gian thực hiện chương trình

Cau 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.

Trả lời:

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

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

Câu hỏi

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

Trả lời:

a) T1=1+n//3=1+1000000//3 đơn vị 

b) T2=1+1+(n//3)=2+1000000//3 đơn vị 

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

Trả lời:

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

Hoạt động 2. Tìm hiểu khái niệm độ phức tạp thời gian thuật toán

Câu 1: 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.

Trả lời:

Thuật toán là một chuỗi các bước được thiết kế để giải quyết một vấn đề cụ thể. Phân loại dựa trên độ phức tạp thời gian của thuật toán:

• O(1) (độ phức tạp thời gian hằng số): thời gian thực thi không thay đổi theo kích thước đầu vào, cố định, vì vậy độ phức tạp thời gian là hằng số. 

• O(log n) (độ phức tạp thời gian logarithmic): thời gian thực thi tăng theo logarit của kích thước đầu vào, thường được sử dụng trong các bài toán tìm kiếm nhị phân, các thuật toán chia để trị, hoặc các thuật toán sắp xếp hiệu quả như QuickSort hoặc MergeSort.

• O(n) (độ phức tạp thời gian tuyến tính): thời gian thực thi tăng tỷ lệ trực tiếp với kích thước đầu vào. 

• O(n^2) (độ phức tạp thời gian bậc hai): thời gian thực thi tăng theo bình phương của kích thước đầu vào. 

• O(n^k) (độ phức tạp thời gian bậc k): thời gian thực thi tăng theo lũy thừa của kích thước đầu

Câu hỏi 

Câu 1: 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.

Trả lời:

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

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

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. Tìm hiểu một số quy tắc đơn giản tính độ phức tạp thời gian thuật toán

Câu 1: Đọ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.

Trả lời:

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

QT2. Quy tắc nhân:

• Hằng số: O(C.f(n))=O(f(n))

• Hàm số: O(f(n).g(n))=O(f(n)).O(g(n))

Câu hỏi

Câu 1: Á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 = n3 + nlogn + 2n + 1.

b) Tính = 3n4 + 2n2logn + 10.

Trả lời:

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

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

LUYỆN TẬP

Câu 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)

Trả lời:

Để xác định độ phức tạp thời gian cần xem xét số lần lặp của vòng for và các phép toán trong vòng lặp.

Vòng for: Vòng lặp này chạy từ 0 đến n-1, với n là 1.000 → số lần lặp là n (1.000 lần).

Các phép toán:

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

Phép toán i*(i+1): là phép nhân và cộng, độ phức tạp là O(1).

→ tổng độ phức tạp thời gian là O(n), hay O(1.000)

Câu 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)

Trả lời:

Chương trình trên tính số lần lặp cần thiết để i lớn hơn n bằng cách nhân i với 2 trong mỗi lần lặp, sau đó tăng biến sum lên 1. Để xác định độ phức tạp thời gian cần xem xét số lần lặp của vòng while và các phép toán trong vòng lặp.

Vòng while: chạy cho đến khi i >= n, giá trị ban đầu của i là 1. Trong mỗi lần lặp, i được nhân với 2 → số lần lặp là log2(n) 

Các phép toán:

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

Phép gán sum = sum + 1: là phép gán giá trị vào biến sum, độ 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

Câu 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.

Trả lời:

• Số lần so sánh: cố định, không phụ thuộc vào dữ liệu đầu vào, là n(n-1)/2, với n là số phần tử trong mảng hoặc danh sách.

• Số lần hoán: 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ử.

Câu 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.

Trả lời:

• 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 

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 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 thời điểm kết thúc

end_time = time.perf_counter()

# Tính thời gian 

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 chương trình 2 là O(n2).