Nội dung text Bài 24. Đánh giá độ phức tạp thời gian thuật toán.pptx
CHÀO MỪNG CẢ LỚP ĐẾN VỚI BÀI HỌC HÔM NAY!
KHỞI ĐỘNG Quan sát Hình 24.1, chúng ta dễ thấy phép nhân hai số có n chữ số sẽ cần n2 phép nhân và 2n phép cộng, vậy tổng số các phép tính đơn của phép nhân này là n2 + 2n, chúng ta nói độ phức tạp thời gian của phép nhân này có bậc n2.
Quan sát và ước lượng thời gian thực hiện các đoạn chương trình 1 và 2 trong Hình 24.2. Chương trình nào chạy nhanh hơn? Vì sao? Chương trình 1: Chương trình 2: 1 n = 100 C = 0 for k in range (n): C = C + 1 print(C) 1 n = 100 C = 0 for i in range (n): for j in range(n): C = C + 1 print(C) Hình 24.2