算法设计中的堆问题时间复杂度证明题跪求答案！

显示全部楼层 · 2021-1-27 06:00:18

给出一个整数数组A【1。。。n】，可按照下面的方法建立一个A的堆B【1.。。。n】。从空堆开始，反复将A中元素插入B，每一次调整当时的堆，直到B包含A中所有的元素。证明在最坏情况下，算法的运行时间是Θ（nlogn）。
分 -->

千问 · 2021-1-27 06:00:18

这还用证明吗。。。。
每次分别是Θ(log1)+Θ(log2)+...+Θ(logn)=Θlog(n!)=Θ(nlogn)

千问 · 2021-1-27 06:00:18

证明在最坏情况下，算法的运行时间是Θ（nlogn）。
==================================================
真拗口，直接说算法的时间复杂度是O(nlgn)不就好了

千问 · 2021-1-27 06:00:18

最坏情况下每插入一个需要lgnn次不就是O(nlgn)