Bài giảng Cơ sở dữ liệu giải thuật: Bài 2 - Phân tích thuật toán

Bài giảng Cơ sở dữ liệu giải thuật: Bài 2 - Phân tích thuật toán nêu lên tính đúng đắn, tính hiệu quả của thuật toán; đo thời gian chạy bằng thực nghiệm; thời gian chạy tốt nhất, trung bình, xấu nhất; vấn đề đánh đổi không gian và thời gian; sử dụng kí hiệu ô lớn.
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sở dữ liệu giải thuật: Bài 2 - Phân tích thuật toán Bài 2: Phân tích thu t toán Gi ng viên: Hoàng Th i p Khoa Công ngh Thông tin – i h c Công Ngh A principle to respect whenever you program: Pay attention to the cost! http://introcs.cs.princeton.edu/java/41analysis/ diepht@vnu 2 M c tiêu bài h c • • • • • Thu t toán: tính úng n, tính hi u qu o th i gian ch y b ng th c nghi m Th i gian ch y t t nh t, trung bình, x u nh t V n ánh i không gian và th i gian S d ng kí hi u ô l n – nh nghĩa hình th c – Các c p th i gian ch y – K thu t ánh giá thu t toán b i ký hi u ô l n • Thu t toán không quy • Thu t toán quy diepht@vnu 3 Gi i thu t nào t t hơn? int factorial (int n) { if (n