Học Algorithms, Ngày 03

Hôm nay học Week 1 Analysis of Algorithms [introduction] & [observations]. Phần này nói về việc phân tích các thuật toán.

Ghi lại một vài ý mà tôi cho là quan trọng.

1.[introduction]

Lý do tại sao cần phải phân tích thuật toán :

• Predict performance.
• Compare algorithms.
• Provide guarantees.
• Primary practical reason : avoid performance bugs.

Phân tích thuật toán như thế nào? Một trong các cách là dùng scientific method, nghĩa là dùng phương pháp khoa học. Gồm các bước chính sau :

• Observe some feature of the natural world.
• Hypothesize a model that is consistent with the observations.
• Predict events using hypothesis.
• Verify the predictions by making futher observations.
• Validate by repeating until the hypothesis and observations agree.

2.[observations]

Sử dụng phương pháp quan sát để mô hình hóa việc tính toán thời gian chạy với kích cỡ dữ liệu đầu vào.

Hầu hết được tính theo công thức : T(N) = aN^b

Từ các kết quả chạy chương trình thực tế, tính toán a và b. Dự đoán b bằng cách gấp đôi số liệu dữ liệu đầu vào, phương pháp "doubling hypothesis". So sánh tỷ lệ kết quả các lần chạy, tính log cơ số 2, -> tính được b.

Hypothesis. Running time is about a N^b with b = lg ratio

Sau đó tính a bằng cách thay vào công thức T(N) và kết quả từ việc chạy chương trình thực tế.

Sau đó so sánh lại kết quả thực tế và kết quả dự đoán cho tới khi 2 kết quả này gần nhau nhất có thể.

Một vài lưu ý nhỏ về việc ảnh hưởng của các tham số:

System independent effects.
・Algorithm.
・Input data.

System dependent effects.
・Hardware: CPU, memory, cache, …
・Software: compiler, interpreter, garbage collector, …
・System: operating system, network, other apps, …

Hôm sau học Week 1 Analysis of Algorithms [mathematical models]