Biết cách phân tích, đánh giá độ phức tạp thuật toán là kĩ năng quan trọng của người thiết kế thuật toán và chương trình. Các quy tắc đơn giản tính độ phức tạp thời gian mang lại cho em điều gì khi đánh giá thuật toán?

Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n²)

T=O(n)+O(n²)=O(n²)Top of Form

1.Thuật toán tìm kiếm tuần tự:

- Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự là O(n)

- Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n = 1 giây * (10⁶ us / phép tính) = 10⁶

- Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n = 1 phút * (60 giây / phút) * (10⁶us / phép tính) = 6 * 10⁷

- Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n = 1 giờ * (60 phút / giờ) * (60 giây / phút) * (10⁶us / phép tính) = 3.6 * 10⁹

2.Thuật toán sắp xếp chèn:

- Độ phức tạp thời gian của thuật toán sắp xếp chèn là O(10²

- Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n = sqrt(1 giây * (10⁶us / phép tính)) =10³

- Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n = sqrt(1 phút * (60 giây / phút) * (10⁶us / phép tính)) = 6 * 10⁴

- Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (10⁶us / phép tính)) = 3.6 * 10⁶

3. Thuật toán sắp xếp chọn:

- Độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n2)

- Giá trị lớn nhất của n là: n = sqrt(1 giây * (10⁶us / phép tính)) = 1000.

Thời gian thực thi là 1 phút:

Giá trị lớn nhất của n là: n = sqrt(1 phút * (60 giây / phút) * (10⁶us / phép tính)) = 60000.

Thời gian thực thi là 1 giờ:

Giá trị lớn nhất của n là: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (10⁶us / phép tính)) = 3.6 * 10⁶Bottom of Form