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

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?

• Đúng

• Sai

Thuật toán tối ưu là gì?

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

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

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

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

Chương trình nào chạy nhanh hơn?

• Chương trình 1

• Chương trình 2

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

• • Hiệu quả về thời gian

• • Hiệu quả về không gian

• • Khả thi khi cài đặt

• • Tất cả đều đúng

Tiêu chuẩn lựa chọn thuật toán là gì?

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

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

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

• • Cả 3 ý đều đúng

Khi nào thì thời gian chạy chương trình được tính bằng tổng đơn vị thời gian thực hiện của mỗi bước lặp?

• Lệnh đơn

• Lệnh if

• Vòng lặp for hoặc while

• Các phép toán đơn giản và phép toán lôgic

Khi nào thì thời gian chạy chương trình được tính bằng đơn vị thời gian lớn nhất của các lệnh nhánh?

• Lệnh đơn

• Lệnh if

• Vòng lặp for hoặc while

• Các phép toán đơn giản

Sắp xếp các độ phức tạp của một số hàm chuẩn sau theo thứ tự độ phức tạp tăng dần:

O(n!), O(nlogn), O(logn)

• O(n!), O(nlogn), O(logn)

• O(logn), O(nlogn), O(n!)

• O(logn), O(n!), O(nlogn)

• O(n!), O(logn), O(nlogn)

n càng lớn thì (a)   sẽ tăng lên nhưng với tốc độ khác nhau

Hãy xác định độ phức tạp thời gian tính toán cho đoạn chương trình

• O(n)

• O(n+1)

• O(n^3)

• O(n+3)