擅长:python、mysql、java
<p>尽管分而治之的方法保证了最少的比较次数,但程序的实际复杂度取决于程序中执行的操作总数。在</p>
<p>在您的例子中,大约有n/2个函数调用(函数调用的二叉树的叶节点)执行4到5个操作,对内部节点执行大约16个操作(计算所有赋值、算术运算、比较和元组构造)。总共大约有10个操作。在</p>
<p>在第一个程序中,操作的总数基本上是2.x*n(其中x取决于执行的分配数)。在</p>
<p>这加上程序1相对于程序2的操作相对简单,导致在两个程序中观察到的系数为5。在</p>
<p>另外,分治算法的比较次数应该是3n/2,而不是2n/3。在</p>