TAILIEUCHUNG - 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

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Tính chi phí của thuật toán
• Thuật toán Bubble sort
• Thuật toán tính tổng
• Ký hiệu Big O
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• tài liệu Cấu trúc dữ liệu và giải thuật
• giáo trình Cấu trúc dữ liệu và giải thuật
• bài tập Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm