关于最大最小堆的时间复杂度问题！
来源：9-2 线段树基础表示
北京_鲁班七号
2018-10-09
波波老师您好！
关于最大最小堆的时间复杂度问题，您在视频中有提到过Heapify的时间复杂度是N，如果真的是这样，堆排序(O(NlogN))岂不是显得很鸡肋(不考虑数据量的情况下)，现在对这一块有疑问，网上搜资料也被弄得很晕！
建立堆的方式在视频中有两种，一种是传统的for循环add，这个时间复杂度是nlogn，但是优化的Heapify是n，测试方法也有体现出效率区别，但是堆排序nlogn的话，这一块如何去比较和heapify的效率区别呢？望波波老师解惑！
1回答
-
liuyubobobo
2018-10-09
可以使用比较大的数据量测试一下，对于同样的数据n，使用两种不同的方式创建n，堆排序的时间效率是可以看出差距的：）
从大O的角度，是看不出这个效率差距的。因为大O是一个极其粗略的性能描述，而不是精确地性能描述。T = 2n也是O(n)，T=10000n也是O(n)。从大O的角度，二者都是O(n)的，但实际，这二者性能差异是巨大的。不要说这样了，就算一个O(n^2)的算法，一个O(nlogn)的算法，在特定情况下，O(n^2)也可能是比O(nlogn)快的。因为大O描述的是n趋向于无穷时的时间变换趋势，所以叫做“渐进时间复杂度”。在我的《算法与数据结构》课程中，对于归并排序或者快速排序，当子区间比较小的时候，转而使用插入排序进行优化，就是这个道理：）
如果一定要从大O的角度看，就要拆开堆排序中的建堆和排序两部。建堆过程，一个是O(n)的，一个是O(nlogn)的。排序过程，二者都是O(nlogn)的。所以，一个是O(n + nlogn)的，一个是O(nlogn + nlogn)的。但还是要明确：从大O的角度：O(n + nlogn) = O(nlogn)，因为对于大O来说，低阶项忽略不计：）
加油！：）
032018-10-09
相似问题