回路运行时间分析

Question

考虑以下循环：

def func1(xs, ys, zs):
    for x in xs:
        for y in ys:
            pass

        for z in zs:
            pass

运行时间应该是size of xs * (size of ys + size of zs)，可以用big-o表示法写成O(X) * (O(Y) + O(Z))。你知道吗

def func2(xs, ys, zs):
    for y in ys:
        for x in xs:
            pass

    for z in zs:
        for x in xs:
            pass

这个函数的运行时间应该是size of ys * size of xs + size of zs * size of xs，这将使Big-O，O(Y) * O(X) + O(Z) * O(X)。你知道吗

问题是，这些运行时分析是否正确？如果是，那么这些函数的运行时间是否相等？因为来自算术x * (y + z) = x * y + x * z。你知道吗

ipython的%timeit函数的结果表明我似乎错了。你知道吗

In [8]: ys1 = range(1, 500)

In [9]: zs1 = range(1, 1000)

In [11]: xs1 = range(1, 1000000)

In [12]: %timeit func1(xs1, ys1, zs1)
1 loop, best of 3: 15.7 s per loop

In [13]: %timeit func2(xs1, ys1, zs1)
1 loop, best of 3: 19.1 s per loop

想知道我的分析有什么问题。谢谢。你知道吗

Answer 1

您所测量的是for循环本身执行所需的时间，而不是循环中的假想语句。你知道吗

当循环的结构如下：

for x in xs:
    for y in ys:
        pass

    for z in zs:
        pass

考虑每个列表的迭代次数：

• xs从外循环迭代一次
• ys在内部循环中迭代X次
• zs在内环中迭代X次

所以总的迭代次数是X * (1 + Y + Z)，它扩展到X + XY + XZ

其中，pass语句的执行次数是X * (Y+Z)或XY + XZ，这与总迭代次数不同。你知道吗

如果循环的结构是这样的：

for y in ys:
    for x in xs:
        pass

for z in zs:
    for x in xs:
        pass

• ys从第一个外循环迭代一次
• xs在第一个内部循环中迭代Y次
• zs从第二个外循环迭代一次
• xs在第二个内部循环中迭代Z次

意思是迭代的总次数是Y*(1+X) + Z*(1 + X)，它扩展到XY + XZ + Y + Z，这与第一个方程有很大的不同。你知道吗

但是执行的pass语句的数目是相同的：XY + XZ

所以基本上：实际执行的语句的数量是相同的，但是第二个例子的迭代次数（获取列表的下一个元素）通常更大，并且由于pass花费的时间比for循环开销少，后者是您实际测量的。你知道吗

Answer 2

您想使用O(x * (y + x))而不是O(X) * (O(Y) + O(Z))（其中x是x的长度，y是y的长度，等等）来描述第一个循环的复杂性（O应该“包装”整个表达式）

为什么？你知道吗

假设f（x）是一个函数，它返回执行大小为x的任务所需的确切操作数

根据定义f（x）=O（x），如果存在a，b，那么a*O（x）+b=f（x）表示所有x（注意，这也意味着对于所有O（x），所有a、所有b、所有c和所有d，a * O(x) + b=c * O(x) + d）。要理解为什么这意味着您需要对表达式进行O包装，请考虑以下循环：

for i in range(n):
    for j in range(n):
        pass #  This is assumed to be exactly one action

注意，对于这个循环，f（n）正好等于n^2

假设我们决定这个循环的复杂性是O(n) * O(n)，而不是O(n ^ 2)。然后，O(n)^2=(a*O(n)+b)^2=a^2 * O(n) + a * b * O(n) + b ^ 2。您可以注意到在扩展中出现了a ^ 2 * O(n)。由于O（n）明显地随输入大小而变化，因此不可能加上或减去这样的常数，使得这个表达式始终等于f（n）。因此，这是错误的表示法。你知道吗

O（n^2）是正确的，因为对于a=1和b=1，a*O(n)+b=f(n)对于所有n

因此，我们需要重写所有循环的复杂性，记住这一点。对于第一个循环，正确的复杂性是O(x * (y + z))=O(x*y + x*z)。对于第二个循环，正确的复杂度是O（yz+zx）。你知道吗

所以是的，两个循环的总体复杂性是相同的。你知道吗