a) Chứng minh n = O(n2)
Sách bài tập Tin học 11 Bài 24: Đánh giá độ phức tạp thời gian thuật toán - Kết nối tri thức
Câu 24.9 trang 77 SBT Tin học 11:
a) Chứng minh n = O(n2).
b) Chứng minh n2 = O(n).
Lời giải:
a) Vì hiển nhiên n < n với n > 1 nên suy ra n = O(n).
b) Nếu như n2 = O(n) thì ta phải có n2 < C.n với n đủ lớn, nhưng từ bất đẳng thức này suy ra n < C. Mâu thuẫn. Vậy suy ra n = O(n).
Lời giải sách bài tập Tin học 11 Bài 24: Đánh giá độ phức tạp thời gian thuật toán hay khác:
Câu 24.1 trang 75 SBT Tin học 11: Giả sử một chương trình P mô tả một thuật toán nào đó ....
Câu 24.2 trang 76 SBT Tin học 11: : Đánh giá thời gian chạy của chương trình sau ....
Câu 24.3 trang 76 SBT Tin học 11: Đánh giá thời gian chạy của chương trình sau ....