tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Phân tích thuật toán

Chương này trang bị cho người học những kiến thức về phân tích thuật toán. Các nội dung chính trong chương này gồm có: Phân tích thuật toán; mô hình RAM; tốt nhất, tồi nhất, trung bình; ký hiệu O‐lớn; tốc độ tăng và tính thống trị; phân tích tiệm cận; một số tính chất của phân tích O‐lớn. . | PHAN TICH THUẬT TOÁN REVIEW a Lần lượt chọn các phần tử trong s theo thứ tự từ trái qua phải nếu chúng phù hợp thuật toán first-fit . b Lần lượt chọn các phần tử trong s theo thứ tự từ nhỏ đến lớn thuật toán best-fit . c Lần lượt chọn các phần tử trong s theo thứ tự từ lớn nhất đến nhỏ nhất. 1 10 2011 REVIEW Bài toán Cho một tập các số nguyên s sl s2 . sn và một giá trị đích T. Tìm một tập con của s sao cho tổng các số trong tập con đó đúng bằng T. Ví dụ Tôn tại một tập con trong s 1 2 5 9 10 mà tổng là T 22 nhưng lại không tồn tại với T 23. Tìm phản ví dụ cho các thuật toán sau NÔI DUNG Phân tích thuật toán Mô hình RAM Tốt nhất tồi nhất trung bình Ký hiệu O-lớn Phân tích tiệm cận Tốc độ tăng và tính thống trị Một số tính chất của phân tích O-lớn 1 PHÂN TÍCH THUẬT TOÁN Bài toán tìm phần tử lớn nhất thứ k Đầu vào Dãy số gồm n số nguyên a a2 . an và số nguyên k 0 k n Đầu ra Giá trị phần tử lớn nhất thứ k trong dãy. Có 2 thuật toán A B để giải bài toán. Với n 100 000 k 100 A cài đặt bằng c chạy mất 12 s B cài đặt bằng java chạy mất 19 s Thuật toán A tốt hơn B MÔ HÌNH RAM Thực hiện thuật toán trên một máy tính giả định gọi là Random Access Machine hoặc RAM. Mỗi phép tính đơn giản - if call thực hiện trong 1 đơn vị thời gian hoặc 1 bước . Vòng lặp hàm thủ tục là kết hợp của nhiều phép tính đơn lẻ Mỗi bước truy cập bộ nhớ mất 1 đơn vị thời gian Luôn có đủ bộ nhớ cần thiết để thực hiện thuật toán Đánh giá thời gian thực hiện thuật toán bằng cách đếm số đơn vị thời gian cần. 1 10 2011 PHÂN TÍCH THUẬT TOÁN Đánh giá hiệu quả của thuật toán mà không cần cài đặt. 2 mô hình Mô hình RAM Random Access Machine Phân tích tiệm cận độ phức tạp trong trường hợp tồi nhất Đánh giá thuật toán dự đoán các tài nguyên mà thuật toán cần. Tài nguyên Thời gian CPU bộ nhớ băng thông phần cứng. 2 TỐT NHẤT TỒI NHẤT VÀ TRUNG BÌNH Độ phức tạp trong trường hợp tồi nhất worst-case complexity Là số lượng bước lớn nhất thuật toán cần thực hiện với bất cứ đầu vào kích thước n nào. Độ phức tạp trong .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Phân tích thuật toán
• Mô hình RAM
• Phân tích tiệm cận
• Phân tích O‐lớn
• Ký hiêu O lớn
• 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
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• 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
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp