tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Tính chi phí của thuật toán

Bài giảng Cấu trúc dữ liệu và giải thuật: Tính chi phí của thuật toán có nội dung trình bày về chi phí của thuật toán, big-O, chi phí của các giải thuật, bài tập tính chi phí của giải thuật Bubble sort, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | Cấu trúc dữ liệu amp Giải thuật Data Structures and Algorithms Tính chi phí của thuật toán Nội dung 1 Chi phí của thuật toán 2 Big-O Big- Big- 09 2013 2 C Nguyen Tri Tuan - Chi phí của các giải thuật Tính tổng n số nguyên sum 0 for i 0 i lt n i sum i Thuật toán Bubble sort for i n-1 i gt 0 i- for j 1 j a j temp a j-1 a j-1 a j a j temp 3 Chi phí của thuật toán 1 6 Cùng một vấn đề có thể giải quyết bằng nhiều giải thuật khác nhau VD. Sắp xếp mảng Bubble sort Heap sort Quick sort Mỗi giải thuật có chi phí cost khác nhau Chi phí thường được tính dựa trên thời gian time bộ nhớ space memory Chi phí thời gian thường được quan tâm nhiều hơn 4 Chi phí của thuật toán 2 6 Tuy nhiên việc dùng khái niệm thời gian theo nghĩa đen vd. giải thuật A chạy trong 10s là không ổn vì tuỳ thuộc vào loại máy tính vd. máy Dual-Core sẽ chạy nhanh hơn Pentium II tuỳ thuộc ngôn ngữ lập trình vd. Giải thuật viết bằng C Pascal có thể chạy nhanh gấp 20 lần viết bằng Basic LISP Do đó người ta thường dùng đơn vị đo logic vd. số phép tính thay cho đơn vị đo thời gian thật mili-giây giây VD. Chi phí thời gian để sắp xếp mảng n phần tử bằng giải thuật Bubble sort là n2 thao tác 5 Chi phí của thuật toán 3 6 VD. Xem đoạn code sau sum 0 for i 0 i Chi phí của thuật toán 4 6 Người ta thường chỉ quan tâm đến chi phí giải thuật với giả định số phần tử cần xử lý rất lớn n Như vậy ta có thể bỏ qua các thành phần rất bé trong biểu thức chi phí VD. f n n2 100n log10n 1000 Việc xác định chi phí chính xác cho một giải thuật rất khó khăn thậm chí nhiều khi không thể ta có thể bỏ qua các thành phần phụ ảnh hưởng không đáng kể VD. for i 0 iChi phí của thuật toán 5 6 Mức tăng của các thành phần trong f n n2 100n log10n 1000 8 Chi phí của thuật toán 6 6 Trường hợp tốt nhất Best case Không phản ánh được thực tế Trường hợp trung bình Average case Rất khó xác định vì lệ thuộc nhiều yếu tố khách quan Trường hợp xấu nhất Worst case Cho chúng ta một sự bảo đảm tuyệt đối VD. Chi phí thuật toán sẽ không nhiều