Lý thuyết Tin học 11 Bài 24 (Kết nối tri thức): Đánh giá độ phức tạp thời gian thuật toán

Lý thuyết Tin học 11 Bài 24: Đánh giá độ phức tạp thời gian thuật toán

A. Lý thuyết Đánh giá độ phức tạp thời gian thuật toán

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

- Không cần cài đặt và chạy chương trình.

- Tính tổng thời gian các phép tính đơn và các lệnh đơn của chương trình.

- Không chính xác hoàn toàn như thời gian thực.

- Dùng để so sánh và ước lượng thời gian chạy chương trình khá chính xác.

- Coi tất cả các lệnh đơn và các phép tính đơn có thời gian chạy như nhau, được gọi là một đơn vị thời gian.

- Đơn giản hoá cách phân tích thời gian tính toán và bảo đảm độ chính xác của tính toán.

- Chương trình 1: Gọi T1 là thời gian chạy của chương trình này.

+ Lệnh tại dòng 1 và 2 cần 1 đơn vị thời gian.

+ Vòng lặp tại dòng 3 có n bước lặp, mỗi bước của vòng lặp sẽ thực hiện lệnh tại dòng 4, lệnh này cần 1 đơn vị thời gian.

+ Tổng thời gian của vòng lặp 3 là n thời gian.

+ Lệnh cuối tại dòng 5 cần 1 đơn vị thời gian.

+ T1 = T1(n) = n + 3 đơn vị thời gian.

- Chương trình 2: Gọi T2 là thời gian chạy của chương trình này.

+ Lệnh tại dòng 1 và 2 cần 1 đơn vị thời gian.

+ Hai vòng lặp lồng nhau tại dòng 3, 4 có n2 bước lặp. Mỗi bước lặp sẽ thực hiện lệnh tại dòng 5, lệnh này cần 1 đơn vị thời gian.

+ Tổng thời gian của vòng lặp 3, 4 là n2 đơn vị thời gian.

+ Lệnh cuối tại dòng 6 cần 1 đơn vị thời gian.

+ T2 = T2(n) = n2 + 3 đơn vị thời gian.

- Lưu ý về phép toán tích cực trong chương trình:

+ Phép toán được thực hiện nhiều nhất và đóng vai trò chính khi tính thời gian, được gọi là phép toán tích cực.

+ Ví dụ trong chương trình 1, phép cộng c = c + 1 tại dòng 4 là phép toán tích cực.

+ Trong chương trình 2, phép cộng c = c + 1 tại dòng 6 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

- Độ phức tạp thời gian của thuật toán 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.

- Phân loại thuật toán dựa trên ước lượng độ phức tạp thời gian.

- Độ phức tạp thời gian có thể coi là một hàm số T(n) với n là số tự nhiên đại diện cho dữ liệu đầu vào.

- Giá trị của T(n) được xác định trên cơ sở số lượng phép toán/câu lệnh cần thực hiện trong chương trình/thuật toán.

- Kí hiệu O-lớn được sử dụng để so sánh và phân tích bậc của hàm thời gian T(n) khi n tiến tới vô cùng.

- Ví dụ: chương trình 1 có độ phức tạp thời gian bậc n, viết là T1(n) = O(n); chương trình 2 có độ phức tạp thời gian bậc n2, viết là T2(n) = O(n2).

- Định nghĩa kí hiệu O-lớn:

+ f(n) và g(n) là hai hàm có đối số tự nhiên.

+ f(n) = O(g(n)) và nói f(n) có bậc O-lớn của g(n) nếu tồn tại hằng số c > 0 và số tự nhiên n0 > 1 sao cho với mọi n > n0, f(n) < c.g(n).

+ Khi f(n) là O-lớn của g(n) thì có thể viết: f(n) = O(g(n)).

- Ví dụ về độ phức tạp thời gian của hai chương trình:

+ Chương trình 1 ở Hình 24.2 có hàm thời gian T1(n) = n + 3.

+ Chọn c = 2, n0 = 3. Khi n > n0, ta có: T1(n) = n + 3 < n + n = c.n. Do đó, T1(n) = O(n). Chương trình 1 có độ phức tạp thời gian O(n) - tuyến tính.

+ Chương trình 2 ở Hình 24.2 có hàm thời gian T2(n) = n2 + 3.

+ Chọn c = 2, n0 = 2. Khi n > n0, ta có: T2(n) = n2 + 3 < n2 + n02 < n2 + n2 = 2n2 = c.n2. Suy ra T2(n) = O(n2). Chương trình 2 có độ phức tạp thời gian O(n2) - bình phương.

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

- Quy tắc tính đơn giản độ phức tạp thời gian thuật toán:

+ QT1. Quy tắc cộng: O(f(n) + g(n)) = O(max(f(n), g(n))). Áp dụng khi tính độ phức tạp thời gian cho hai chương trình được thực hiện nối tiếp nhau.

+ QT2. Quy tắc nhân: Phép nhân với hằng số: O(C.f(n)) = O(f(n)), với C là hằng số bất kì. Phép nhân với hàm số: O(f(n)g(n)) = O(f(n).O(g(n))). Áp dụng tính độ phức tạp thời gian cho chương trình có hai vòng lặp lồng nhau.

Sơ đồ tư duy Đánh giá độ phức tạp thời gian thuật toán

B. Bài tập Đánh giá độ phức tạp thời gian thuật toán

Câu 1: Các bước giải bài toán trên máy tính được tiến hành theo thứ tự nào sau đây:

A. Xác định bài toán – Lựa chọn thuật toán – Viết chương trình – Hiệu chỉnh – Viết tài liệu

B. Xác định bài toán – Viết chương trình – Lựa chọn thuật toán – Viết tài liệu

C. Lựa chọn thuật toán – Xác định bài toán – Viết chương trình – Hiệu chỉnh – Viết tài liệu

D. Viết chương trình – Hiệu chỉnh – Viết tài liệu

Câu 2: Mỗi bài toán được đặc tả bởi mấy thành phần:

A. 4

B. 3

C. 2

D. 1

Câu 3: Viết chương trình là?

A. Biểu diễn thuật toán

B. Dùng ngôn ngữ lập trình để diễn đạt bài toán

C. Dùng ngôn ngữ lập trình và cấu trúc dữ liệu thích hợp để diễn tả thuật toán

D. Tất cả đều đúng

Câu 4: Tiêu chuẩn lựa chọn thuật toán:

A. Lượng tài nguyên thuật toán đòi hỏi và lượng tài nguyên cho phép

B. Độ phức tạp của thuật toán

C. Các tài nguyên như thời gian thực hiện, số lượng ô nhớ…

D. Cả 3 ý trên đều đúng

Câu 5: Giải bài toán trên máy tính được tiến hành qua mấy bước?

A. 3

B. 4

C. 5

D. 6

Câu 6: Tiêu chí lựa chọn hoặc thiết kế thuật toán là?

A. Hiệu quả về thời gian

B. Hiệu quả về không gian

C. Khả thi khi cài đặt

D. Tất cả đều đúng

Câu 7: Bước quan trọng nhất để giải một bài toán trên máy tính là

A. Lựa chọn hoặc thiết kế thuật toán

B. Viết chương trình

C. Xác định bài toán

D. Hiệu chỉnh

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

A. Sai

B. Đúng

C. Ý kiến khác

D. Chưa đủ dữ kiện

Câu 9: Mục đích của việc hiệu chỉnh là:

A. Xác định lại Input và Output của bài toán

B. Phát hiện và sửa sai sót

C. Mô tả chi tiết bài toán

D. Để tạo ra một chương trình mới

Câu 11: Thuật toán tối ưu là?

A. Sử dụng ít thời gian, ít bộ nhớ…

B. Sử dụng ít thời gian, nhiều bộ nhớ, ít phép toán…

C. Sử dụng nhiều thời gian, nhiều bộ nhớ, ít phép toán…

D. Sử dụng ít thời gian, ít bộ nhớ, ít phép toán…

Trắc nghiệm Tin học 11 Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Câu 1: Độ phức tạp thời gian của phép nhân hai số nguyên có nnn chữ số, như trong ví dụ của Karatsuba, là bao nhiêu?

A. O(n)O(n)O(n)

B. O(nlog⁡n)O(n \log n)O(nlogn)

C. O(n2)O(n^2)O(n2)

D. O(n1.585)O(n^{1.585})O(n1.585)

Câu 2: Trong chương trình 1 ở Hình 24.2, tổng số đơn vị thời gian để thực hiện toàn bộ chương trình là bao nhiêu?

A. 2+n+1=n+32 + n + 1 = n + 32+n+1=n+3

B. n2+2n^2 + 2n2+2

C. 2n+32n + 32n+3

D. n2+3n^2 + 3n2+3

Câu 3: Trong chương trình 2 ở Hình 24.2, độ phức tạp thời gian của vòng lặp lồng nhau là gì?

A. O(n)O(n)O(n)

B. O(log⁡n)O(\log n)O(logn)

C. O(n2)O(n^2)O(n2)

D. O(1)O(1)O(1)

Câu 4: Ký hiệu O(n)O(n)O(n) trong phân tích độ phức tạp thời gian biểu thị điều gì?

A. Chương trình có độ phức tạp tuyến tính

B. Chương trình có độ phức tạp bình phương

C. Chương trình có độ phức tạp mũ

D. Chương trình có độ phức tạp hàng số

Câu 5: Quy tắc cộng trong tính độ phức tạp thời gian của thuật toán được áp dụng trong trường hợp nào?

A. Khi có vòng lặp lồng nhau

B. Khi thực hiện hai chương trình nối tiếp nhau

C. Khi thực hiện phép toán nhân

D. Khi thực hiện phép toán chia

Câu 6: Nếu chương trình có độ phức tạp thời gian T(n)=n2+3n+1T(n) = n^2 + 3n + 1T(n)=n2+3n+1, độ phức tạp thời gian của nó là gì?

A. O(n2)O(n^2)O(n2)

B. O(n)O(n)O(n)

C. O(log⁡n)O(\log n)O(logn)

D. O(n3)O(n^3)O(n3)

Câu 7: Độ phức tạp thời gian của thuật toán sắp xếp chọn là bao nhiêu?

A. O(n)O(n)O(n)

B. O(log⁡n)O(\log n)O(logn)

C. O(n2)O(n^2)O(n2)

D. O(nlog⁡n)O(n \log n)O(nlogn)

Câu 8: Trong trường hợp nào độ phức tạp thời gian của chương trình là O(1)O(1)O(1)?

A. Khi chương trình có vòng lặp lồng nhau

B. Khi chương trình chỉ có các phép toán đơn và không phụ thuộc vào nnn

C. Khi chương trình có độ phức tạp tuyến tính

D. Khi chương trình có độ phức tạp lũy thừa

Câu 9: Ký hiệu O(log⁡n)O(\log n)O(logn) được dùng khi độ phức tạp thời gian của thuật toán là gì?

A. Tuyến tính

B. Logarit

C. Đa thức

D. Mũ

Câu 10: Để tính độ phức tạp thời gian của chương trình với các phép toán lồng nhau, ta áp dụng quy tắc nào?

A. Quy tắc cộng

B. Quy tắc nhân

C. Quy tắc chia

D. Quy tắc cộng và chia

PHẦN II. Câu trắc nghiệm đúng sai. Thí sinh trả lời từ câu 1 đến câu 2. Trong mỗi ý a), b), c), d) ở mỗi câu, thí sinh chọn đúng hoặc sai

Câu 1: Độ phức tạp thời gian của chương trình 1 trong Hình 24.2, với tổng thời gian tính toán là T1(n)=n+3T_1(n) = n + 3T1​(n)=n+3, được đánh giá là:

a) O(1)

b) O(log n)

c) O(n)

d) O(n²)

Câu 2: Độ phức tạp thời gian của chương trình 2 trong Hình 24.2, với tổng thời gian tính toán là T2(n)=n2+3T_2(n) = n^2 + 3T2​(n)=n2+3, được đánh giá là:

a) O(n)

b) O(n²)

c) O(log n)

d) O(1)

PHẦN III. Câu trả lời ngắn. Thí sinh trả lời từ câu 1 đến câu 3

Câu 1: Độ phức tạp thời gian của chương trình 1 trong hình 24.2 là gì?

Câu 2: Độ phức tạp thời gian của chương trình 2 trong hình 24.2 là gì?

Câu 3: Tại sao việc ước lượng thời gian chạy của chương trình lại quan trọng trong lập trình?

Xem thêm các bài lý thuyết Tin học 11 sách Kết nối tri thức hay, chi tiết tại:

Lý thuyết Bài 21: Các thuật toán sắp xếp đơn giản

Lý thuyết Bài 23: Kiểm thử và đánh giá chương trình

Lý thuyết Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

Lý thuyết Bài 28: Thiết kế chương trình theo Mô đun

Lý thuyết Bài 30: Thiết lập thư viện cho chương trình

Xem thêm tài liệu Tin học lớp 11:

Giải Tin học 11 Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Giải SBT Tin học 11 Bài 24: Đánh giá độ phức tạp thời gian thuật toán