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
Nội dung trích xuất từ 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 h a n g e Vi h a n g e Vi XC XC e e F- F- w wPD PD er er ! ! W W O O N N y y bu bu to to Giải thuật Sắp xếp k k lic lic C Cw w m m w ww w o o .c .c .d o .d o c u -tr a c k c u -tr a c k Chỉ số 1 2 3 4 5 6 7 8 9 10 Ban 5 6 2 2 10 12 9 10 9 3 2 253 6 35 10 đầu 2 3 2 6 5 12 9 10 9 10 Heap 10 2 ...