Giải chi tiết sách bài tập SBT Tin học 11 định hướng khoa học máy tính Kết nối tri thức bài 25 Xác định độ phức tạp thời gian thuộc toán. ConKec sẽ hướng dẫn giải tất cả câu hỏi và bài tập với cách giải nhanh và dễ hiểu nhất. Hi vọng, thông qua đó học sinh được củng cố kiến thức và nắm bài học tốt hơn.
Bài tập & Lời giải
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.6. Nếu f(n) = O(g(n)) thì có suy ra được g(n) = O(f(n)) hay không?
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}$)