使用递归算法下heapify的复杂度问题

Question

为了排除复杂度干扰去掉了排序验证的操作直接验证的插入的时间复杂度

在3000W条数据（100W数据差距太小 可能电脑CPU计算能力比较好吧）

执行递归：false,isHeapify：false,执行时间为：2.545800285

执行递归：false,isHeapify：true,执行时间为：1.884151106

执行递归：true,isHeapify：false,执行时间为：1.718195152

执行递归：true,isHeapify：true,执行时间为：1.578124216

 再使用递归算法下 好像没有一半的差距。

Answer 1

liuyubobobo 2018-07-05 03:09:57

首先，heapify的时间复杂度是O(n)的，不断插入的时间复杂度是O(nlogn)的，他们之间的差距理论分析不是一半的关系。

其次，复杂度描述的是上界，是一个理论工具，但在算法性能的实际测量中，最大的问题是忽略了实现过程中的常数项和低阶项。这使得对于一组数据，同样复杂度的算法，实测性能相差巨大；或者两个不同复杂度的算法，实测性能相差不大，甚至对于一定的规模表现出相反的时间消耗结果，这些都是正常的。

所以，如果你看过我的《算法与数据结构》，对于高级排序算法（归并排序或者快速排序），我们在递归到n比较小的情况下，会转而使用插入排序法进行优化。为什么要转而使用一个O(n^2)的算法来优化O(nlogn)的算法？就是这个原因：）

最后，由于现代计算机从底层硬件指令的集成，到操作系统的运行环境，再到所使用的语言编译器的不同，使得我们写出的程序，真正测试出的结果，携带了很多这种外部环境带来的影响，而不是100%取决于我们的算法本身。实际上，你只列出了一组测试数据，重复执行一遍，估计差距不小：）

综上，印象中，我在这个课程中提到过，实测的时间是帮助大家感性认识算法性能的，可以大致看出不同算法之间的差别。但切不可对实测时间毫秒级别的差距较真。

如果一定想较真：

1）不要使用大O做时间复杂度分析，而是使用精准的数学表达式，计算出针对你的具体写法，算法基本指令执行的步骤是多少（对于随机数据计算期望）。这样计算，其实还是有对“什么是基本指令”的定义问题（比如我们通常会认为加法和乘法都是基本质量，但在计算机内部，这二者执行效率还是不同。）但如果看具体时间的话，比使用大O精准多了。印象里《算法导论》基于几个简单的算法进行了这样的分析。有兴趣可以参考。但是，对于稍微复杂一点的算法，这样的分析都是极其繁多，在实践中没有必要的：）

2）我在《玩转算法面试》中介绍了一个数据倍增法验证复杂度的方式，在数据规模较大的情况下，能比较好的反应一个算法的复杂度增长趋势。

3）复杂性理论本身是一个专门的领域，如果对这方面感兴趣，可以看更多专门论述这个领域的教材或者资料：）

加油！

• 提问者 xiaocui_0001 #1

  多谢老师。