Video
Phân tích thuật toán không đệ quy từng bước: phép toán cơ bản và tỉ số T(2n)/T(n)
Nếu dữ liệu gấp đôi, thuật toán chạy lâu gấp mấy lần?
Hoạt động
Sinh viên dự đoán rồi tự đo tỉ số T(2n)/T(n) để nhận ra bậc tăng của một đoạn mã.
Đưa một đoạn mã mới có ba vòng lặp lồng nhau. Bạn dự đoán tỉ số trước khi chạy và giải thích vì sao. Với n = 10, 20, 40 số phép tính là 120, 1 140, 9 880, tỉ số gần 8 và đang tiến về 8.
Nếu lớp có máy, cho các bạn tự viết đoạn mã đếm. Không có máy thì thầy cô đọc sẵn bảng kết quả sau khi lớp đã dự đoán.