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<br /> Gi ng viên: Hoàng Th i p<br /> Khoa Công ngh Thông tin –<br /> i h c Công Ngh<br /> <br /> A principle to respect whenever you program:<br /> <br /> Pay attention to the cost!<br /> http://introcs.cs.princeton.edu/java/41analysis/<br /> <br /> diepht@vnu<br /> <br /> 2<br /> <br /> M c tiêu bài h c<br /> •<br /> •<br /> •<br /> •<br /> •<br /> <br /> Thu t toán: tính úng n, tính hi u qu<br /> o th i gian ch y b ng th c nghi m<br /> Th i gian ch y t t nh t, trung bình, x u nh t<br /> V n<br /> ánh i không gian và th i gian<br /> S d ng kí hi u ô l n<br /> –<br /> nh nghĩa hình th c<br /> – Các c p<br /> th i gian ch y<br /> – K thu t ánh giá thu t toán b i ký hi u ô l n<br /> • Thu t toán không<br /> quy<br /> • Thu t toán<br /> quy<br /> <br /> diepht@vnu<br /> <br /> 3<br /> <br /> Gi i thu t nào t t hơn?<br /> int factorial (int n) {<br /> if (n