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ừ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Gọi T(n) là thời gian thực hiện của chương trình. Thời gian chạy của chương trình được phân tích như sau:
– Lệnh gán tại dòng 2 cần 1 đơn vị thời gian.
– Vòng for tại dòng 3, biến i chạy từ 1 đến n, nên vòng lặp có n bước lặp.
– Với mỗi bước lặp trên, chương trình thực hiện
• Vòng lặp tại dòng 4, biến j chạy từ 1 đến i, nên vòng lặp thực hiện i bước lặp. • Với mỗi bước lặp:
a Chương trình thực hiện vòng lặp tại dòng 5, biến k chạy từ j đến j + vòng lặp có i + 1 bước lặp.
a Với mỗi bước lặp chương trình thực hiện 1 lệnh gán tại dòng 6 cần 1 đơn vị thời gian.
– Lệnh trả về tại dòng 7 cần 1 đơn vị thời gian.
Tổng hợp lại, hàm trên có thời gian chạy là
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = n + 2log n.
c) T(n) = 2100
b) T(n) = n2 + 3nlogn + 2n.
d) T(n) = 2n+1.
Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = n + 2log n.
c) T(n) = 2100
b) T(n) = n2 + 3nlogn + 2n.
d) T(n) = 2n+1.
Xem đáp án »
13/07/2024
1,766
Câu 2:
Em hãy xác định thời gian chạy T(n) của thuật toán sắp xếp chèn sau, với n là độ dài của dãy A.
Em hãy xác định thời gian chạy T(n) của thuật toán sắp xếp chèn sau, với n là độ dài của dãy A.
Xem đáp án »
27/11/2023
1,036
Câu 3:
Cho biết thuật toán sau thực hiện công việc gì và hãy xác định độ phức tạp
thời gian của thuật toán.
1 def findMax(A):
2 maxVal = A[0]
Cho biết thuật toán sau thực hiện công việc gì và hãy xác định độ phức tạp
thời gian của thuật toán.
1 def findMax(A):
2 maxVal = A[0]
Xem đáp án »
13/07/2024
617
Câu 4:
Cho biết hàm sau thực hiện công việc gì và hãy xác định độ phức tạp thời gian của chương trình.
Cho biết hàm sau thực hiện công việc gì và hãy xác định độ phức tạp thời gian của chương trình.
Xem đáp án »
27/11/2023
264
về câu hỏi!