Nếu f(n) = O(g(n)) thì có suy ra được g(n) = O(f(n)) hay không?

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

a) T(n) = n + 2logn

b) T(n) = n$^{2}$ +3nlogn + 2n

c) T(n) = 2$^{100}$

d) T(n) = 2$^{n+1}$

Xem lời giải

Bài 25.2. Cho biết thuật toán sau thực hiện công việc gì và hãy xác định độ phức tạp thời gian của thuật toán.

Xem lời giải

Bài 25.3. Cho biết hàm sau thực hiện công việc gì và hãy xác định độ phức tạp thời gian của chương trình.

Xem lời giải

Bài 25.4. Em hãy xác định thời gian chạy T(n) của thuật toán sắp xếp chèn sau, với n là độ dài của dãy A.

Xem lời giải

Bài 25.5. Xác định độ phức tạp thời gian của hàm sau:

Xem lời giải

Bài 25.7.* Giả sử f(n) = $a_{k}n^{k}+a_{k-1}n^{k-1}+...+a_{1}n+a_{0}$. Chứng minh rằng f(n) = O(n$^{k}$)

Xem lời giải