关于最大最小堆的时间复杂度问题！

Question

波波老师您好！
关于最大最小堆的时间复杂度问题，您在视频中有提到过Heapify的时间复杂度是N，如果真的是这样，堆排序(O(NlogN))岂不是显得很鸡肋(不考虑数据量的情况下)，现在对这一块有疑问，网上搜资料也被弄得很晕！
建立堆的方式在视频中有两种，一种是传统的for循环add，这个时间复杂度是nlogn，但是优化的Heapify是n，测试方法也有体现出效率区别，但是堆排序nlogn的话，这一块如何去比较和heapify的效率区别呢？望波波老师解惑！

Answer 1

liuyubobobo 2018-10-09 12:07:15

可以使用比较大的数据量测试一下，对于同样的数据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来说，低阶项忽略不计：）

加油！：）

• 提问者 北京_鲁班七号 #1

  那heapify和堆排序，哪个优呢，如果说heapify是按照堆的排序去建立堆的话，那么经过heapify的数组，其实已经是一个排好序的堆了，就不需要再创建堆后，再去堆排序吧

• 提问者 北京_鲁班七号 #2

  视频中提到的2种创建堆的方法，其实都已经有对堆进行排序了，不需要再去排序了吧，这是否和堆排序是矛盾的

• liuyubobobo 回复 提问者 北京_鲁班七号 #3

  heapify是创建堆的过程，没有进行排序。一个堆的数组表示，不是有序的：）