2

我正在比较 maxmin 算法实现的复杂性，我以两种方式实现：蛮力方式和分而治之的方式。在我为 1000000 和 10000000 之间的十个元素输入测试了这两种算法之后。遵循以下算法：

下面的蛮力实现：

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)

和下面的分而治之的实现：

def maxmin4(vetor,inicio,fim):
    if ((fim - inicio) == 1):
        return (vetor[inicio], vetor[inicio])
    elif ((fim - inicio) == 2):
        if( vetor[inicio] < vetor[inicio+1]):
            return (vetor[inicio], vetor[inicio+1])
        else:
            return (vetor[inicio+1], vetor[inicio])
    else:
        (min_left,max_left) = maxmin4(vetor,inicio,(fim-inicio)/2 + inicio)
        (min_right,max_right) = maxmin4(vetor,(fim-inicio)/2 + inicio,fim)
        if (max_left < max_right):
            max = max_right
        else:
            max = max_left
        if (min_left < min_right):
            min = min_left
        else:
            min = min_right
    return (min,max)

结果：

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，理论上第一个比第二个慢。为什么会发生？

4

3 回答 3

4

事实证明，您的代码中似乎确实存在错误或分析中存在错误——但这并不重要。我会在最后谈到它。

如果您查看您的结果，很明显两者之间存在大约 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))

…您可以看到该模式成立：

     100: 0.00002003 0.00010014 (x5.00000000)
    1000: 0.00017500 0.00080800 (x4.61716621)
   10000: 0.00172400 0.00821304 (x4.76393307)
  100000: 0.01630187 0.08839488 (x5.42237660)
 1000000: 0.17010999 0.76053309 (x4.47083153)
10000000: 1.77093697 8.32503319 (x4.70092010)

那么，为什么第二个版本的恒定开销更高呢？嗯，第一个版本只是做一个简单的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 倍。最后，这并不会真正影响分析。

于 2013-09-18T17:36:35.223 回答
3

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

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

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

这与程序 1 中的操作相对于程序 2 的相对简单性一起导致在两个程序中观察到的因子为 5。

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

于 2013-09-18T18:25:51.177 回答
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__and的对象序列__gt__，并让这些方法更新全局计数器。

于 2013-09-18T19:22:34.970 回答