CHƯƠNG 6: KĨ THUẬT LẬP TRÌNH

BÀI 24: ĐÁNH GIÁ ĐỘ PHỨC TẠP THUẬT TOÁN

( 10 câu)

1. NHẬN BIẾT (2 câu)

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:

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

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

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

2. THÔNG HIỂU ( 2 câu)

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

Khẳng định "Trong mọi chương trình chỉ có đúng một phép toán tích cực" là 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. Một phép toán được xem là tích cực khi nó đóng góp vào sự hoàn thành tác vụ của chương trình và tối ưu hóa hiệu suất. Các phép toán tích cực có thể bao gồm tính toán số học, truy xuất dữ liệu, ghi ra tập tin, hiển thị thông báo cho người dùng và nhiều hơn nữa.

Câu 2: Xác định độ phức tạp thời gian của thuật toán sắp xếp chọn

Trả lời:

Số lần so sánh giữa các phần tử: Trong thuật toán sắp xếp chọn, số lần so sánh giữa các phần tử là cố định, không phụ thuộc vào dữ liệu đầu vào. Cụ thể, số lần so sánh trong thuật toán sắp xếp chọn 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 đổi giữa các phần tử: Trong thuật toán sắp xếp chọn, 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ử.

3. VẬN DỤNG (4 câu)

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

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

Trả lời:

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

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

Tính = n³ + 5n - 3.

Trả lời:

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

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

Tính = n³+ nlogn + 2n + 1.

Trả lời:

O(n³) + 1.

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

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

Trả lời:

3O(n⁴ + 10)

4. VẬN DỤNG CAO ( 2 câu)

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:

Chương trình trên tính tổng các giá trị i*(i+1) trong khoảng từ 0 đến n-1 và lưu kết quả vào biến s. Để xác định độ phức tạp thời gian của chương trình này, ta 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. Vậy số lần lặp là n, hay 1.000 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)

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ủa chương trình này, ta 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: Vòng lặp này chạy cho đến khi i >= n, và giá trị ban đầu của i là 1. Trong mỗi lần lặp, i được nhân với 2, vậy số lần lặp là log2(n) (vì sau mỗi lần nhân i với 2, giá trị của i sẽ gấp đôi). Ví dụ, nếu n = 1000 thì số lần lặp là log2(1000) ≈ 10.

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)