Luyện tậpCâu hỏi 2. Xác định độ phức tạp thời gian tính toán cho chương trình sau:n = 1000Sum = ...
Câu hỏi:
Luyện tập
Câu hỏi 2. Xác định độ phức tạp thời gian tính toán cho chương trình sau:
n = 1000
Sum = 0
i = 1
While i <n;
i = i*2
Sum = Sum + 1
Print (Sum)
Câu trả lời:
Người trả lời: GV. Đỗ Đăng Linh
Độ phức tạp thời gian tính toán cho chương trình trên là O(log n), với n = 1000 thì độ phức tạp là O(log 1000) ≈ O(10). Điều này cho thấy rằng chương trình có độ phức tạp thời gian tăng dần theo logarit của input, đồng thời cũng cho thấy rằng thời gian thực thi của chương trình không tăng tuyến tính theo input mà tăng theo cấp số nhân logarit của input.
Câu hỏi liên quan:
- Khởi độngCâu hỏi. Quan sát và ước lượng thời gian thực hiện các đoạn chương trình 1 và 2 trong Hình...
- 1. Đánh giá thời gian thực hiện chương trìnhHoạt động 1: Tìm hiểu cách đánh giá thời gian thực hiện...
- Câu hỏi 1. Các lệnh và đoạn chương tình sau cần chạy trong bao nhiêu đơn vị thời gian?
- Câu hỏi 2. Khẳng định "Trong mọi chương trình chỉ có đúng một phép toán tích cực" lá đúng hay sai?
- 2. Phân tích độ phức tạp thời gian của thuật toánHoạt động 2: Tìm hiểu khái niệm độ phức tạp thời...
- Câu hỏi . Tính độ phức tạp của các hàm thời gian sau:a) Tính = 2n(n - 2) + 4.b) Tính = $n^{3}$ + 5n...
- 3. Một số quy tắc thực hành tính độ phức tạp của thuật toánHoạt động 3: Tìm hiểu một số quy tắc đơn...
- Câu hỏi. Áp dụng các quy tác trên để tính độ phức tạp của các hàm thời gian sau:a) Tính =...
- Luyện tậpCâu hỏi 1. Xác định độ phức tạp thời gian cho chương trình sau:n = 1000s = 0for i in...
- Vận dụngCâu hỏi 1. Xác định độ phức tạp thời gian của thuật toán sắp xếp chọn đã được học trong bài...
- Vận dụngCâu hỏi 2. Em hãy thiết lập chương trình và tính thời gian chạy thực tế trên máy tính của...
Bình luận (0)