tailieunhanh - Giáo trình phân tích khả năng vận dụng kĩ thuật đánh giá giải thuật theo phương pháp tổng quan p9

Tham khảo tài liệu 'giáo trình phân tích khả năng vận dụng kĩ thuật đánh giá giải thuật theo phương pháp tổng quan p9', kỹ thuật - công nghệ, tự động hoá phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 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 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. 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 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 . BINSORT 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. 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. Trang 39 Sắp xếp 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 được gọi là các bin