TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Phân tích thuật toán - Nguyễn Mạnh Hiển (HKI năm 2020-2021)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Phân tích thuật toán" cung cấp cho người học các kiến thức: Phân tích thuật toán là gì, các ký hiệu tiệm cận, tốc độ tăng của các hàm, các ví dụ phân tích thuật toán. | Phân tích thuật toán Algorithm Analysis Nguyễn Mạnh Hiển hiennm@ 2 Nội dung 1. Phân tích thuật toán là gì 2. Các ký hiệu tiệm cận 3. Tốc độ tăng của các hàm 4. Các ví dụ phân tích thuật toán 3 1. Phân tích thuật toán là gì 4 Phân tích thuật toán Nhằm xác định thời gian chạy độ phức tạp của thuật toán dưới dạng một hàm f của kích thước đầu vào n. Ví dụ Thời gian tìm kiếm tuần tự một phần tử x trong một dãy n phần tử là f n n phép so sánh trong trường hợp tồi xấu nhất . Đơn vị thời gian Không phải là giờ phút giây. Mà là thao tác cơ bản ví dụ cộng nhân so sánh Mỗi thao tác cơ bản có thời gian chạy là hằng một lượng thời gian nhỏ không phụ thuộc vào kích thước đầu vào n . 5 Đếm số thao tác cơ bản Nhận diện các thao tác cơ bản trong thuật toán. Xác định thao tác cơ bản T chiếm nhiều thời gian chạy nhất so với các thao tác cơ bản còn lại. Thao tác T này thường xuất hiện trong các vòng lặp. Đếm số lần thực hiện thao tác T sẽ thu được hàm thời gian chạy f n . Chú ý Trong trường hợp khó tìm ra thao tác T có thể đếm tất cả các thao tác cơ bản. Khi đó sẽ thu được hàm f n f n nhưng nếu áp dụng thêm phép phân tích tiệm cận học sau thì các kết quả cuối cùng sẽ giống nhau. 6 Ví dụ đếm số thao tác cơ bản Ví dụ 1 In các phần tử C Ví dụ 3 Kiểm tra tính sắp xếp C for i 0 i lt n i template cout 7 2. Các ký hiệu tiệm cận 8 Phân tích tiệm cận Nhằm xem xét tốc độ tăng của hàm f n khi n dần tới . Cho phép quy các dạng hàm f n khác nhau về một số ít dạng cơ bản như log n n n2 Giúp so sánh cỡ thời gian chạy của các thuật toán dễ hơn. Có 3 cách phân tích tiệm cận tương ứng với ba ký hiệu tiệm cận sau đây Ô lớn O tìm cận trên của f n Ô-mê-ga lớn tìm cận dưới của f n Tê-ta lớn tìm cận chặt của f n 9 Ký hiệu O f n O g n khi và chỉ khi c gt 0 và n0 gt 0 sao cho f n cg n n n0 cg n f n f n bị chặn trên bởi g n theo nghĩa tiệm cận n0 10 Ký hiệu f n g n khi và chỉ khi c gt 0 và n0 gt 0 sao cho cg n f n n n0 f n cg n f n bị chặn dưới bởi g n theo nghĩa tiệm cận n0 11 Ký hiệu f n g n khi .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Bài giảng Cấu trúc dữ liệu
• Phân tích thuật toán
• Ký hiệu tiệm cận
• Tốc độ tăng của các hàm
• 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
• 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