Posted by haifeng on 2015-06-13 13:49:51 last update 2015-06-13 13:49:51 | Edit | Answers (1)
在堆排序的过程中, 每次弹出根结点(也就是 deleteMin)的时间复杂度为多少?
整个堆排序过程的时间复杂度是多少?
1
Posted by haifeng on 2015-06-13 13:54:42
deleteMin 的时间复杂度是 $O(\log N)$, 总共是 $N$ 个结点, 所以堆排序的时间复杂度是 $O(N\log N)$.