Quan sát Hình 24.1 chúng ta dễ thấy phép nhân hai số có n chữ số sẽ cần n² phép nhân và 2n phép cộng, vậy tổng số các phép tính đơn của phép nhân này là n² + 2n, chúng ta nói độ phức tạp thời gian của phép nhân này có bậc n².

Hình 24.1

Năm 1960, trong một tiết dạy về công nghệ thông tin, nhà toán học Nga, Viện sĩ Kolmogorov đã hỏi các sinh viên của mình là có ai tìm được cách tính phép nhân trên với thời gian tốt hơn bậc n² được không? Khi đó đây là một bài toán chưa có lời giải. Đúng một tuần sau, một sinh viên tên là Karatsuba đã đưa cho Viện sĩ Kolmogorov một lời giải tốt hơn về phép tính nhân trên chỉ với độ phức tạp thời gian bậc n^1,58496.

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?

Hình 24.2

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.

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?

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?

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.

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

a) T(n) = 2n(n – 2) + 4.

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

Á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(n) = n3 + nlogn + 2n + 1.

b) T(n) = 3n4 + 2n2logn + 10.