Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình hướng dẫn kĩ thuật phân tích đánh giá giải thuật theo phương pháp tổng quan p9

Tiếp tục quá trình trên và giải thuật kết thúc sau bước 9, ứng với bước i =2. 2.5.4 Phân tích HeapSort Thời gian thực hiện của HeapSort là O(n logn) Như đã phân tích trong mục 2.5.3.1, thủ tục PushDown lấy O(logn) để đẩy một nút xuống trong cây có n nút. Trong thủ tục HeapSort dòng lệnh {1}-{2}) lặp n/2 lần mà mỗi lần PushDown lấy O(logn) nên thời gian thực hiện | Giải thuật Sắp xếp Chỉ số 1 2 3 4 5 6 7 8 9 10 Ban đầu 5 2 6 2 5 3 2 2 6 10 3 5 12 9 10 9 3 10 Heap 2 10 2 3 2 10 9 6 5 12 9 10 10 9 10 2 i 10 2 9 3 3 9 5 9 6 5 9 12 10 10 9 2 2 i 9 3 10 5 5 10 6 9 6 10 9 12 10 10 3 2 i 8 5 6 9 10 9 12 10 3 Hình 2-17 Hoán đổi a 1 với a 8 và đầy a 1 xuống trong a 1.7 Tiếp tục quá trình trên và giải thuật kết thúc sau bước 9 ứng với bước i 2. 2.5.4 Phân tích HeapSort Thời gian thực hiện của HeapSort là O n logn Như đã phân tích trong mục 2.5.3.1 thủ tục PushDown lấy O logn để đẩy một nút xuống trong cây có n nút. Trong thủ tục HeapSort dòng lệnh 1 - 2 lặp n 2 lần mà mỗi lần PushDown lấy O logn nên thời gian thực hiện 1 - 2 là O n logn . Vòng lặp 3 - 4 - 5 lặp n-1 lần mỗi lần PushDown lấy O logn nên thời gian thực hiện của 3 - 4 - 5 là O n logn . Tóm lại thời gian thực hiện HeapSort là O n logn . 2.6 BINSORT 2.6.1 Giải thuật Nói chung các giải thuật đã trình bày ở trên đều có độ phức tạp là O n2 hoặc O nlogn . Tuy nhiên khi kiểu dữ liệu của trường khoá là một kiểu đặc biệt việc sắp xếp có thể chỉ chiếm O n thời gian. Sau đây ta sẽ xét một số trường hợp. 2.6.1.1 Trường hợp đơn giản Giả sử ta phải sắp xếp một mảng A gồm n phần tử có khoá là các số nguyên có giá trị khác nhau và là các giá trị từ 1 đến n. Ta sử dụng B là một mảng cùng kiểu với A và phân phối vào phần tử b j một phần tử a i mà a i .key j. Khi đó mảng B lưu trữ kết quả đã được sắp xếp của mảng A. Ví dụ 2-7 Sắp xếp mảng A gồm 10 phần tử có khoá là các số nguyên có giá trị là các số 4 7 1 2 5 8 10 9 6 và 3 Ta sử dụng mảng B có cùng kiểu với A và thực hiện việc phân phối a 1 vào b 4 vì a 1 .key 4 a 2 vào b 7 vì a 2 .key 7 a 3 vào b 1 vì a 3 .key 1 . Hình sau minh họa cho việc phân phối các phần tử của mảng a vào mảng b. Nguyễn Văn Linh Trang 39 Hình 2-18 Phân phối các phân tử a i vào các bin b j Để thực hiện việc phân phối này ta chỉ cần một lệnh lặp for i 1 to n do b a i .key a i Đây cũng là lệnh chính trong chương trình sắp xếp. Lệnh này lấy O n thời gian. Các phần tử b j .