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.
Dựa vào kiến thức trong bài kết hợp kiến thức thực tế của bản thân để trả lời câu hỏ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))
Advertisements (Quảng cáo)
# 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).