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.

Câu hỏi trong đề: Giải SBT Tin học 11 KNTT Bài 25. Thực hành xác định độ phức tạp thời gian thuật toán có đáp án !!

Sách mới 2k7: Bộ 20 đề minh họa Toán, Lí, Hóa, Văn, Sử, Địa…. form chuẩn 2025 của Bộ giáo dục (chỉ từ 49k/cuốn).

Đề toán-lý-hóa Đề văn-sử-địa Tiếng anh & các môn khác

Quảng cáo

Trả lời:

Giải bởi Vietjack

Gọi n là kích thước của mảng, T(n) là thời gian thực hiện của thuật toán. Thời gian chạy của thuật toán được phân tích như sau:

– Câu lệnh tại dòng 2 cần 1 đơn vị thời gian.

– Vòng lặp for tại dòng 3 biến i chạy từ 1 đến n − 1, nên vòng lặp có n – 1 bước lặp.

– Với mỗi bước lặp chương trình thực hiện:

• Hai lệnh gán tại dòng 4 và 5.

• Vòng lặp while tại dòng 6. Vòng lặp này sẽ chạy tối đa là i lần. Mỗi lần lặp chương trình sẽ thực hiện hai lệnh gán tại dòng 7 và 8, cần 2 đơn vị thời gian. • Lệnh gán tại dòng 9 cần 1 đơn vị thời gian.

Tổng hợp lại chương trình trên có thời gian chạy tối đa là:

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. (ảnh 2)

Nhà sách VIETJACK:

Xem thêm kho sách »

Combo - Sổ tay kiên thức trọng tâm Toán, Lí, Hóa dành cho 2k7 VietJack

₫29.000 (Đã bán 152)

Sách - Tuyển tập 30 đề thi đánh giá năng lực Đại học Quốc gia Hà Nội 2025 cho 2k7 VietJack

₫140.000 ₫300.000 (Đã bán 1,2k)

Sách Combo - Tuyển tập 30 đề thi đánh giá năng lực Đại học Quốc gia TP Hồ Chí Minh (2 cuốn) - 2025 cho 2k7 VietJack

₫140.000 ₫300.000 (Đã bán 1,6k)

Sách - Tuyển tập 15 đề thi Đánh giá tư duy Đại học Bách Khoa Hà Nội 2025 cho 2k7 VietJack

₫140.000 ₫300.000 (Đã bán 2,7k)

Bình luận

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.

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

Câu 2:

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 828

Câu 3:

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

Xem đáp án » 27/11/2023 502

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.

Xem đáp án » 27/11/2023 338

Câu 5:

Giả sử f(n) = an* + a,.n*?

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

Câu 6:

Nếu f(n) = O(g(n)) thì có suy ra được g(n) = O(f(n)) hay không?

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

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