<p>事实证明,你的代码中确实有一个bug或者你的分析中有一个错误,但这并不重要。我会在最后完成的。在</p>
<p>如果你看一下你的结果,很明显两者之间有5倍的恒定差。这意味着第二个算法的复杂度并不比第一个差,它只是有一个更高的常数乘数,你在做同样数量的步骤,但每一步都要做更多的工作。在</p>
<hr/>
<p>有可能这只是你测试如此狭窄范围的人工制品,只有10的单一因子。但是使用更广泛的值来运行测试,例如:</p>
<pre><code>for i in 100, 1000, 10000, 100000, 1000000, 10000000:
v = [random.random() for _ in range(i)]
t1 = timeit.timeit(lambda: maxmin1(v), number=1)
t2 = timeit.timeit(lambda: maxmin4(v, 0, len(v)), number=1)
print('{:8}: {:.8f} {:.8f} (x{:.8f})'.format(i, t1, t2, t2/t1))
</code></pre>
<p>…你可以看到这种模式是成立的:</p>
^{pr2}$
<hr/>
<p>那么,为什么第二个版本的常量开销更高呢?第一个版本只是做一个简单的<code>for</code>迭代,两个比较,每个元素分配一个。第二种是调用函数、构建和分解元组、进行更多的比较等等,这肯定会比较慢。如果你想知道为什么它慢了5倍(或者说,实际上是15倍,如果你在做2n/3步而不是2n步),你需要做一些分析,或者至少看看字节码。但我觉得不值得。在</p>
<hr/>
<p>这个故事的寓意是,2(n-1)和2n/3-2都是O(n)是有原因的:当你有两个不同的复杂度类,比如O(n)和O(n**2),这对大n总是有影响;当你在同一个类中有两个算法时,实现中的常量(每一步的成本)很容易超过常量在步数中。在</p>
<hr/>
<p>同时,如何验证2n/3-2分析?很简单,只需添加一个全局计数器,每次调用maxmin4时递增一次。以下是预期和实际结果:</p>
<pre><code> 100: 65 127
1000: 665 1023
10000: 6665 11807
100000: 66665 131071
1000000: 666665 1048575
10000000: 6666665 11611391
</code></pre>
<p>但这仅仅意味着你要做2/3的步骤,而不是1/3,因此每个步骤的固定成本是7.5倍而不是15倍。最后,这并不会真正影响分析。在</p>