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

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

Sách bài tập Tin học 11 Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán - Kết nối tri thức

Câu 25.6 trang 78 SBT Tin học 11: Nếu f(n) = O(g(n)) thì có suy ra được g(n) = O(f(n)) hay không?

Lời giải:

Không. Ví dụ f(n) = n, g(n) = n2 thì rõ ràng f(n) = O(g(n)) nhưng ngược lại không đúng.

Lời giải sách bài tập Tin học 11 Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán hay khác:

• Câu 25.1 trang 77 SBT Tin học 11: Tính độ phức tạp của các hàm thời gian sau ....

• Câu 25.2 trang 77 SBT Tin học 11: 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 ....

• Câu 25.3 trang 78 SBT Tin học 11: 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 ....

• Câu 25.4 trang 78 SBT Tin học 11: 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 ....

• Câu 25.5 trang 78 SBT Tin học 11: Xác định độ phức tạp thời gian của hàm sau ....

• Câu 25.7 trang 78 SBT Tin học 11: Giả sử f(n) = an* + a,.n*? ....