Câu hỏi:

20/04/2023 227

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.

Xem lời giải

Câu hỏi trong đề: Giải SGK Tin học 11 KNTT Bài 24. Đánh giá độ phức tạp thời gian thuật toán có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

*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).

Sách thầy cô Vietjack biên soạn

Xem thêm »

Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay

Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

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)

Xem đáp án » 13/07/2024 1,985

Câu 2:

Xác định độ phức tạp thời gian cho chương trình sau:

n = 1000

s = 0

for i in range (n);

s = s + i*(i+1)

print (s)

Xem đáp án » 13/07/2024 1,943

Câu 3:

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?

Xem đáp án » 13/07/2024 1,745

Câu 4:

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?

Xem đáp án » 13/07/2024 1,165

Câu 5:

Tính độ phức tạp của các hàm thời gian sau:

a) T(n) = 2n(n - 2) + 4.

b) T(n) = n³ + 5n - 3.

Xem đáp án » 13/07/2024 1,069

Câu 6:

Á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(n) = n³ + nlogn + 2n + 1.

b) T(n) = 3n⁴ + 2n²logn + 10.

Xem đáp án » 13/07/2024 741

Câu 7:

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 21.

Xem đáp án » 13/07/2024 530

Xem thêm các câu hỏi khác »

Hỏi bài tập

Đăng ký gói thi VIP

VIP +1 tháng ( 199,000 VNĐ )

VIP +1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP +3 tháng ( 299,000 VNĐ )

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP +6 tháng ( 399,000 VNĐ )

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP +12 tháng ( 499,000 VNĐ )

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

Siêu tiết kiệm - Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

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.

Bình luận

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)

Xác định độ phức tạp thời gian cho chương trình sau: n = 1000 s = 0 for i in range (n); s = s + i*(i+1) print (s)

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?

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?

Tính độ phức tạp của các hàm thời gian sau: a) T(n) = 2n(n - 2) + 4. b) T(n) = n3 + 5n - 3.

Á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(n) = n3 + nlogn + 2n + 1. b) T(n) = 3n4 + 2n2logn + 10.

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 21.

VIP +1 tháng ( 199,000 VNĐ )

VIP +3 tháng ( 299,000 VNĐ )

VIP +6 tháng ( 399,000 VNĐ )

VIP +12 tháng ( 499,000 VNĐ )

🔥 Đề thi HOT:

CHỌN BỘ SÁCH BẠN MUỐN XEM

Đăng ký

Đăng nhập

Quên mật khẩu

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)

Xác định độ phức tạp thời gian cho chương trình sau:

n = 1000

s = 0

for i in range (n);

s = s + i*(i+1)

print (s)

Tính độ phức tạp của các hàm thời gian sau:

a) T(n) = 2n(n - 2) + 4.

b) T(n) = n³ + 5n - 3.

Á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(n) = n³ + nlogn + 2n + 1.

b) T(n) = 3n⁴ + 2n²logn + 10.