Câu hỏi:

20/04/2023 215

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.

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 !!

Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa... kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 70k).

Tổng ôn Toán-lý hóa Văn-sử-đia Tiếng anh & các môn khác

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

Nhà sách VIETJACK:

Xem thêm kho sách »

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

Đã bán 244

₫ 136.000 ₫ 58.000

Hà Nội

Trọng tâm Sử, Địa, GD KTPL 11 cho cả 3 bộ Kết nối, Chân trời, Cánh diều VietJack - Sách 2025

Đã bán 104

₫ 136.000 ₫ 38.000

Hà Nội

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

Đã bán 1k

₫ 104.000 ₫ 52.000

Hà Nội

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

Đã bán 218

₫ 130.000 ₫ 75.000

Hà Nội

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,754

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,663

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,616

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,055

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 940

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 653

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 500

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.

Nhà sách VIETJACK:

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.

🔥 Đề 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.