Câu hỏi:
20/04/2023 246
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 các chương trình 1 và 2 ở Hình 24.2 với các giá trị n khác nhau từ đó thấy được ý nghĩa sự khác biệt độ phức tạp thời gian của hai chương trình này.
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 các chương trình 1 và 2 ở Hình 24.2 với các giá trị n khác nhau từ đó thấy được ý nghĩa sự khác biệt độ phức tạp thời gian của hai chương trình này.
Quảng cáo
Trả lời:
*Chương trình 1:
from collections import Counter
import time
n = 1000
c = 0
# Ghi lại thời điểm bắt đầu
start_time = time.time()
for k in range(n):
c = c + 1
# Ghi lại thời điểm kết thúc
end_time = time.time()
# Tính thời gian hoàn thành
elapsed_time = end_time - start_time
# Sử dụng hàm Counter để đếm số lần lặp
counter = Counter(range(n))
# In số lần lặp
print("Số lần lặp: {}".format(counter))
# In thời gian thực thi
print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))
*Chương trình 2:
import time
n = 1000
c = 0
# Ghi lại thời điểm bắt đầu
start_time = time.perf_counter()
for k in range(n):
for j in range(n):
c = c + 1
# Ghi lại thời điểm kết thúc
end_time = time.perf_counter()
# Tính thời gian hoàn thành
elapsed_time = end_time - start_time
# In số lần lặp
print("Số lần lặp: {}".format(c))
# In thời gian thực thi
print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))
àSự khác biệt độ phức tạp thời gian của 2 chương trình trên:
Độ phức tạp thời gian của chương trình 1 là O(1), còn độ phức tạp thời gian của chương trình 2 là O(n2).
Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay
- Sách - Sổ tay kiến thức trọng tâm Vật lí 11 VietJack - Sách 2025 theo chương trình mới cho 2k8 ( 45.000₫ )
- Trọng tâm Hóa học 11 dùng cho cả 3 bộ sách Kết nối, Cánh diều, Chân trời sáng tạo VietJack - Sách 2025 ( 58.000₫ )
- Sách lớp 11 - Trọng tâm Toán, Lý, Hóa, Sử, Địa lớp 11 3 bộ sách KNTT, CTST, CD VietJack ( 52.000₫ )
- Sách lớp 10 - Combo Trọng tâm Toán, Văn, Anh và Lí, Hóa, Sinh cho cả 3 bộ KNTT, CD, CTST VietJack ( 75.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Chương trình trên tính số lần lặp cần thiết để i lớn hơn n bằng cách nhân i với 2 trong mỗi lần lặp, sau đó tăng biến sum lên 1. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng while và các phép toán trong vòng lặp.
Vòng while: Vòng lặp này chạy cho đến khi i >= n, và giá trị ban đầu của i là 1. Trong mỗi lần lặp, i được nhân với 2, vậy số lần lặp là log2(n) (vì sau mỗi lần nhân i với 2, giá trị của i sẽ gấp đôi). Ví dụ, nếu n = 1000 thì số lần lặp là log2(1000) ≈ 10.
Các phép toán trong vòng lặp:
Phép gán i = i * 2: Đây là phép nhân, có độ phức tạp là O(1).
Phép gán sum = sum + 1: Đây là phép gán giá trị vào biến sum, có độ phức tạp là O(1).
Vậy tổng độ phức tạp thời gian của chương trình là O(log n), hay O(log2(1000)) ≈ O(10)
Lời giải
Chương trình trên tính tổng các giá trị i*(i+1) trong khoảng từ 0 đến n-1 và lưu kết quả vào biến s. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng for và các phép toán trong vòng lặp.
Vòng for: Vòng lặp này chạy từ 0 đến n-1, với n là 1.000. Vậy số lần lặp là n, hay 1.000 lần.
Các phép toán trong vòng lặp:
Phép gán s = s + i*(i+1): Đây là phép gán giá trị vào biến s, có độ phức tạp là O(1).
Phép toán i*(i+1): Đây là phép nhân và cộng, có độ phức tạp là O(1).
Vậy tổng độ phức tạp thời gian của chương trình là O(n), hay O(1.000)
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.