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

Lời giải

a) T(n) = n + 2log n ≤ 3n với n ≥ 1. Vậy T(n) = O(n).

b) T(n) = n2 + 3nlogn +2n ≤ 6n với n ≥ 1. Vậy T(n) = O(n). 

c) T(n) = O(1), độ phức tạp hằng số.

d) T(n) = 2n+1 = 2.2" = O(2").

Lời giải

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)

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Vietjack official store
Đăng ký gói thi VIP

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

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

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

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

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

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

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

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay