Bài giảng Cấu trúc dữ liệu và thuật toán

Cài đặt thuật toán với các cấu trúc dữ liệu (tiếp) Phân tích thòi gian tính của thuật toán 9 Vòng lặp for ỏ dòng 1 đòi hỏi thời gian O(|V|) 9 Việc khởi tạo đống min ở dòng 3 đòi hỏi thời gian O(|V|) 9 Vòng lặp while bắt đau từ dòng 4 lặp |V| Ian do đó thao tác Extract-Min thực hiện |V| lan và đòi hỏi thòi gian tông cộng 0(1 V| log |V|) 9 Thao tác vun lại đống Decrease-Key() ở dòng 10 phải thực hiện không quá 0(1 E|) Ian. Do đó thòi gian thực hiện của thao tác này trong thuật toán là O(|E|log|V|) Vậy tổng cộng thời gian tính của thuật toán là O((IE|+1V|)log |V|)