tailieunhanh - BÀI GIẢNG GIẢI THUẬT VÀ LẬP TRÌNH - QUY HOẠCH ĐỘNG - LÊ MINH HOÀNG - 4

Có thể nhận xét thêm là QuickSort đệ quy cần thêm không gian nhớ cho Stack, còn HeapSort ngoài một nút nhớ phụ để thực hiện việc đổi chỗ, nó không cần dùng thêm gì khác. HeapSort tốt hơn QuickSort về phương diện lý thuyết bởi không có trường hợp tồi tệ nào HeapSort có thể mắc phải. Cũng nhờ có HeapSort mà giờ đây khi giải mọi bài toán có chứa mô-đun sắp xếp, ta có thể nói rằng độ phức tạp của thủ tục sắp xếp đó không quá O(nlog2n) | Cấu trúc dữ liệu và Giải thuật 95 thời gian thực hiện trung bình phức tạp hơn ta chỉ ghi nhận một kết quả đã chứng minh được là độ phức tạp trung bình của HeapSort cũng là O nlog2n . Có thể nhận xét thêm là QuickSort đệ quy cần thêm không gian nhớ cho Stack còn HeapSort ngoài một nút nhớ phụ để thực hiện việc đổi chỗ nó không cần dùng thêm gì khác. HeapSort tốt hơn QuickSort về phương diện lý thuyết bởi không có trường hợp tồi tệ nào HeapSort có thể mắc phải. Cũng nhờ có HeapSort mà giờ đây khi giải mọi bài toán có chứa mô-đun sắp xếp ta có thể nói rằng độ phức tạp của thủ tục sắp xếp đó không quá O nlog2n . . SẮP XẾP BẰNG PHÉP ĐẾM PHÂN PHỐI DISTRIBUTION COUNTING Có một thuật toán sắp xếp đơn giản cho trường hợp đặc biệt Dãy khoá ki k2 . kn là các số nguyên nằm trong khoảng từ 0 tới M TKey . Ta dựng dãy c0 c1 . cM các biến đếm ở đây cV là số lần xuất hiện giá trị V trong dãy khoá for V 0 to M do cV 0 Khởi tạo dãy biến đếm for i 1 to n do ck ck 1 Ví dụ với dãy khoá 1 2 2 3 0 0 1 1 3 3 n 10 M 3 sau bước đếm ta có co 2 d 3 c2 2 c3 3. Dựa vào dãy biến đếm ta hoàn toàn có thể biết được sau khi sắp xếp thì giá trị V phải nằm từ vị trí nào tới vị trí nào. Như ví dụ trên thì giá trị 0 phải nằm từ vị trí 1 tới vị trí 2 giá trị 1 phải đứng liên tiếp từ vị trí 3 tới vị trí 5 giá trị 2 đứng ở vị trí 6 và 7 còn giá trị 3 nằm ở ba vị trí cuối 8 9 10 0 0 1 1 1 2 2 3 3 3 Tức là sau khi sắp xếp Giá trị 0 đứng trong đoạn từ vị trí 1 tới vị trí c0. Giá trị 1 đứng trong đoạn từ vị trí c0 1 tới vị trí c0 c1. Giá trị 2 đứng trong đoạn từ vị trí c0 c1 1 tới vị trí c0 c1 c2. Giá trị v trong đoạn đứng từ vị trí c0 c1 . cv-1 1 tới vị trí c0 c1 c2 . cv. Để ý vị trí cuối của mỗi đoạn nếu ta tính lại dãy c như sau for V 1 to M do cV cV-1 cV Thì cV là vị trí cuối của đoạn chứa giá trị V trong dãy khoá đã sắp xếp. Muốn dựng lại dãy khoá sắp xếp ta thêm một dãy khoá phụ x1 x2 . xn. Sau đó duyệt lại dãy khoá k mỗi khi gặp khoá mang giá trị V ta đưa giá trị đó vào khoá xcv và giảm cv đi 1. .

• Cơ sở dữ liệu
• toán kinh tế
• kiến thức thống kê
• giáo trình đại học
• bài giảng chứng khoán
• đề cương ôn tập
• câu hỏi trắc nghiệm
• Đề cương toán kinh tế
• Ôn tập toán kinh tế
• Ôn thi toán kinh tế
• Lý thuyết toán kinh tế
• Kiến thức toán kinh tế
• Nghiên cứu toán kinh tế
• Đáp án Toán kinh tế
• Đề thi Toán kinh tế
• Đề cao học Toán kinh tế
• Đề thi Toán kinh tế 2013
• Đề thi Toán kinh tế 118
• Đề thi sau đại học Toán kinh tế
• Bài thi Toán kinh tế
• Câu hỏi thi Toán kinh tế
• Luyện thi Toán kinh tế
• Nội dung thi Toán kinh tế
• Bài giảng Toán kinh tế
• Tài liệu Toán kinh tế
• Tham khảo Toán kinh tế
• Mô hình toán kinh tế
• Hướng dẫn thi Toán kinh tế
• Tài liệu thi Toán kinh tế
• Mô hình toán
• Phân tích mô hình toán kinh tế
• Phương pháp phân tích toán kinh tế
• Bài tập toán kinh tế
• Bài tập mô hình toán kinh tế
• Bài tập phân tích toán kinh tế
• Học phần Toán kinh tế
• Đề cương học phần Toán kinh tế
• Tìm hiểu Toán kinh tế
• Bài toán Kinh tế
• Đáp án tham khảo Toán kinh tế 2011
• Câu hỏi Toán kinh tế
• Dự toán kinh tế
• Tiểu luận Dự toán kinh tế
• Bài tập Dự toán kinh tế
• Câu hỏi Dự toán kinh tế
• Phương pháp luận của Dự toán kinh tế
• Vai trò của Dự toán kinh tế
• Đề thi cao học Toán kinh tế
• Bài giảng Mô hình Toán kinh tế
• Cấu trúc mô hinh toán kinh tế
• Mô hình toán kinh tế phổ biến
• Mô hình giải tích phân tích kinh tế
• Phân tích kinh tế
• Phân tích kinh doanh
• Mô hình giải tích
• Công cụ toán
• Mô hình kinh tế
• Các phương tiện thanh toán quốc tế
• phương tiện thanh toán quốc tế
• bài giảng phương tiện thanh toán quốc tế
• tài liệu phương tiện thanh toán quốc tế
• nhập môn Kinh tế học Vi mô
• kinh tế vi mô
• kinh tế vĩ mô
• kinh tế phát triển
• kinh tế lượng
• Toán ứng dụng kinh tế
• Giáo trình mô hình toán kinh tế
• Lý thuyết toán học
• Phương pháp mô hình
• Nghiên cứu mô hình toán kinh tế
• Bài giảng Toán kinh tế 1
• Toán kinh tế 1
• Cấu trúc của môn học
• Kinh tế học