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}$
Bài Làm:
a) T(n) = n + 2logn ≤3n với n≥ 1. Vậy T(n) = O(n).
b) T(n) = n$^{2}$ +3nlogn + 2n ≤ 6n$^{2}$ với n≥ 1. Vậy T(n) = O(n$^{2}$)
c) T(n) = O(1), độ phức tạp hằng số
d) T(n) = 2$^{n+1}$ = 2. 2$^{n}$= O(2$^{n}$)
Trong: Giải SBT Tin học 11 định hướng KHMT Kết nối bài 25 Xác định độ phức tạp thời gian thuộc toán
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.
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.
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.
Bài 25.6. Nếu f(n) = O(g(n)) thì có suy ra được g(n) = O(f(n)) hay không?
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 thêm các bài Giải SBT tin học 11 định hướng Khoa học máy tính kết nối tri thức được biên soạn cho Học kì 1 & Học kì 2 theo mẫu chuẩn của Bộ Giáo dục theo sát chương trình Lớp 11 giúp bạn học tốt hơn.
Giải bài tập SGK, SBT, VBT và Trắc nghiệm các môn học Lớp 11, dưới đây là mục lục các bài giải bài tập sách giáo khoa và Đề thi chi tiết với câu hỏi bài tập, đề kiểm tra 15 phút, 45 phút (1 tiết), đề thi học kì 1 và 2 (đề kiểm tra học kì 1 và 2) các môn trong chương trình Lớp 11 giúp bạn học tốt hơn.
