为什么maxmin分而治之的实现比其他maxmin算法慢？

Question

我比较了maxmin算法实现的复杂度，我已经用两种方法实现了：暴力方法和分而治之的方法。在我测试了这两种算法后，对1000000到10000000之间的10个元素输入进行了测试。遵循以下算法：

暴力实施如下：

def maxmin1(vetor):
    max,min = vetor[0],vetor[0];
    for elem in vetor[1:]:
        if elem > max:
            max = elem
        if elem < min:
            min = elem
    return (min,max)

分而治之的实施方法如下：

^{pr2}$

结果是：

input N     time algorithm 1 |  time algorithm 2
1000000 |   0.1299650669     |  0.6347620487 
2000000 |   0.266600132      |  1.3034451008
3000000 |   0.393116951      |  2.2436430454
4000000 |   0.5371210575     |  2.5098109245
5000000 |   0.6094739437     |  3.4496300221
6000000 |   0.8271648884     |  4.6163318157
7000000 |   1.0598180294     |  4.8950240612 
8000000 |   1.053456068      |  5.1900761128
9000000 |   1.1843969822     |  5.6422820091
10000000|   1.361964941      |  6.9290060997

我不明白为什么第一种算法比第二种算法快，因为第一种算法的复杂度为2（n-1），第二种算法的复杂度为3n/2-2，理论上第一种算法比第二种算法慢。为什么会这样？在

Answer 1

看到Python递归比Python迭代运行得更快，我会非常惊讶。试试maxmin的这个实现，一次取两个值。在

def minmax(seq):

    def byTwos(seq):
        # yield values from sequence two at a time
        # if an odd number of values, just return
        # the last value twice (won't hurt minmax
        # evaluation)
        seq = iter(seq)
        while 1:
            last = next(seq)
            yield last,next(seq,last)

    seqByTwos = byTwos(seq)
    # initialize minval and maxval
    a,b = next(seqByTwos,(None,None))
    if a < b:
        minval,maxval = a,b
    else:
        minval,maxval = b,a

    # now walk the rest of the sequence
    for a,b in seqByTwos:
        if a < b:
            if a < minval:
                minval = a
            if b > maxval:
                maxval = b
        else:
            if b < minval:
                minval = b
            if a > maxval:
                maxval = a
    return minval, maxval

如果要对比较进行计数，则传递实现__lt__和{}的对象序列，并让这些方法更新全局计数器。在

Answer 2

尽管分而治之的方法保证了最少的比较次数，但程序的实际复杂度取决于程序中执行的操作总数。在

在您的例子中，大约有n/2个函数调用（函数调用的二叉树的叶节点）执行4到5个操作，对内部节点执行大约16个操作（计算所有赋值、算术运算、比较和元组构造）。总共大约有10个操作。在

在第一个程序中，操作的总数基本上是2.x*n（其中x取决于执行的分配数）。在

这加上程序1相对于程序2的操作相对简单，导致在两个程序中观察到的系数为5。在

另外，分治算法的比较次数应该是3n/2，而不是2n/3。在

Answer 3

事实证明，你的代码中确实有一个bug或者你的分析中有一个错误，但这并不重要。我会在最后完成的。在

如果你看一下你的结果，很明显两者之间有5倍的恒定差。这意味着第二个算法的复杂度并不比第一个差，它只是有一个更高的常数乘数，你在做同样数量的步骤，但每一步都要做更多的工作。在

---

有可能这只是你测试如此狭窄范围的人工制品，只有10的单一因子。但是使用更广泛的值来运行测试，例如：

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))

…你可以看到这种模式是成立的：

^{pr2}$

---

那么，为什么第二个版本的常量开销更高呢？第一个版本只是做一个简单的for迭代，两个比较，每个元素分配一个。第二种是调用函数、构建和分解元组、进行更多的比较等等，这肯定会比较慢。如果你想知道为什么它慢了5倍（或者说，实际上是15倍，如果你在做2n/3步而不是2n步），你需要做一些分析，或者至少看看字节码。但我觉得不值得。在

---

这个故事的寓意是，2（n-1）和2n/3-2都是O（n）是有原因的：当你有两个不同的复杂度类，比如O（n）和O（n**2），这对大n总是有影响；当你在同一个类中有两个算法时，实现中的常量（每一步的成本）很容易超过常量在步数中。在

---

同时，如何验证2n/3-2分析？很简单，只需添加一个全局计数器，每次调用maxmin4时递增一次。以下是预期和实际结果：

     100:         65        127
    1000:        665       1023
   10000:       6665      11807
  100000:      66665     131071
 1000000:     666665    1048575
10000000:    6666665   11611391

但这仅仅意味着你要做2/3的步骤，而不是1/3，因此每个步骤的固定成本是7.5倍而不是15倍。最后，这并不会真正影响分析。在