tailieunhanh - 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. | 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! 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 <= 1) return 1; else return n * factorial(n-1); } int factorial (int n) { if (n<=1) return 1; else { fact = 1; for (k=2; k<=n; k++) fact *= k; return fact; } } diepht@vnu 4 Thu t toán • Thu t toán ư c hi u là s c t chính xác m t dãy các bư c có th th c hi n ư c m t cách máy móc gi i quy t m t v n • Bi u di n thu t toán – mã, gi mã, sơ kh i • Tính úng n (correctness) – òi h i trư c h t • Tính hi u qu (efficiency) – quan tr .