首页 > Python算法 > 认识算法 阅读数:72

简单Python程序的时间复杂度分析

让我们先看一段代码:
def square(n):
    Partial_Sum = 0
    for i in range(1, n + 1):
        Partial_Sum += i * i
    return Partial_Sum

上面是一段求 n 以内自然数的平方和的代码,其时间复杂度的分析也相对简单。代码的第二行只占一次运算,因为变量的声明不计入运算之中而赋值为一次运算。第三行的 for 循环中 i 从 1 加到了 n,其中过程包括 i 的初始化、i 的累加和 i 的范围判断(每执行一次 for 循环其实都要判断 i 是否超过了所定义的范围),分别消耗 1 次运算、n 次运算和 n+1 次运算(当 n 为 n+1 时判断仍会执行,所以从 1 到 n+1 共 n+1 次运算)。

至此,代码的前三行共进行了 2n+3 次运算。第四行是相乘、相加和赋值三个功能的组合的代码,相乘需 n 次运算,相加需 n 次运算,而赋值也需 n 次运算,所以第四行一共进行了 3n 次运算。最后一行返回消耗一次运算。总体来看,这段代码一共需进行 2n+3+3n+1=5n+4 次运算。根据上文的渐进原则,这段代码的时间复杂度为 O(n)。

通过上面的分析,可以看出细致的时间复杂度分析十分烦琐。但毕竟时间复杂度追求渐进原则,所以在这里为大家整理了一下快速算时间复杂度的技巧。

1.循环结构

for i in range(1, k*n+m+1):
    I += 1
上述代码中的 n 为输入规模,k、m 均为已知常数。依旧根据之前的步骤分析时间复杂度:第一行代码是一个 for 循环,一共会进行 2(k*n+m)+2 次运算,而第二行无论多么复杂,也只会进行 din 次运算(d 为一个常数)。我们会发现,for 循环中的运算次数一定在 n 的有限倍数以内。

因此根据渐进原则,只要 for 循环的循环范围是在 n 的有限倍数以内(range 的上界始终可以被表示为 kin+m 的形式),则一个 for 循环的时间复杂度必然为 O(n)。换句话说,我们可以忽略 for 循环里的赋值、比较、增值等操作,而单纯地将这些操作看成一个时间复杂度为 O(n) 的整体。

while(n > 0):
    Partial_Sum += 1
    n -= 1
while 循环和 for 循环其实异曲同工。while 循环中,除没有新声明一个变量 i 并赋初值外,其余的运算几乎和 for 循环相同,所以 while 循环的时间复杂度也为 O(n)。

for i in range(n):
    for j in range(n):
        Partial_Sum += 1
我们将两个 for 循环迭代在一起。现在我们可以大胆假设一个 for 循环的时间复杂度为 O(n),而对于第一行 for 循环中的每一个 i,都会对应 n 个不同的 j,而每一个 j 都会对应 Partial_Sum 的一次相加和赋值。所以在有 n 个不同的 i,每个 i 会对应 n 的不同的j的情况下,会有 n*n=n2 次第三行的操作。

在这里我们可以说这段代码的时间复杂度为 O(n2)。实际上,真实的运算次数会有 k*n2(k 为一个常数)次,其中 k 始终是有限的,尽管 k 有时会非常大。所以当我们考虑 n 趋于无穷的时候,常数因子 k 就可以被忽略了。

for i in range(n):
    Partial_Sum += 1
for i in range(n):
    for j in range(n):
        Partial_Sum *= 2
如果我们把一个单层 for 循环和一个双层 for 循环并列,如上所示的代码的时间复杂度可以计算出为 O(n)+O(n2)=O(n+n2)。当然,由于渐进原则,O(n) 的复杂度可以被忽略,所以整段代码的时间复杂度仍是 O(n2)。

综上所述,我们可以总结出循环结构时间复杂度的一些规律:
  • 无论是 for 还是 while 循环,只要循环的范围可以表示为 k * n+m,则该循环的时间复杂度为 O(n);
  • 如果循环中嵌套循环,则时间复杂度将变成每一层循环的时间复杂度相乘的结果;
  • 如果循环中嵌套循环,则时间复杂度将变成每一层循环的时间复杂度相乘的结果;
  • 在决定时间复杂度时,往往只需要关注层数最多 for 循环结构的时间复杂度,因为其他循环的时间复杂度很大程度上会被忽略。

2.分支结构

所谓分支结构,就是 if…elif(elseif)…else 的结构,一般解决条件不同的平行问题。以下代码即为分支结构的一些例子:
if n % 2 == 0:     #分支S1
    n //= 2
    for i in range(n):
        Partial_Sum += 1
else:          #分支S2
    n -= 1

因为分支即意味着不可兼得,所以绝不可能出现同时进入同一个前提下的两个分支的情况。因此我们可以得出结论,一个分支结构的运行时间绝不会超过前提条件判断的运行时间(如上面代码中的  n%2==0),加上分支结构中较复杂的分支的运行时间(如上面代码中的第一个分支 S1)。

所以面对简单的分支结构,我们可以大胆估计,虽然估计的结果会比实际的大一些。当然,适当的计算也可以使我们的估计更加准确,其也需因情况而定。

3.递归结构

递归,指一个函数的定义中包含了调用自身的语句。通过使用递归,一个复杂的问题可以被转化成一个相似但相对简单的问题,使用少量的代码就可以实现大量相似的运算。

我们都听过一个故事:从前有座山,山上有座庙,庙里有一个小和尚和一个老和尚,老和尚对小和尚说:“从前有座山,山上有座庙,庙里有一个小和尚和一个老和尚,老和尚对小和尚说‘从前有座山,山上有座庙……’”我们无法用有限语言讲完这个故事,但是递归可以帮助我们用有限的代码来完成这项任务,代码如下:
def story():
    print("从前有座山,山上有座庙,庙里有一个小和尚和一个老和尚,老和尚对小和尚说")
    story()
请不要运行这段代码!因为缺少边界条件,所以这是一个无限循环的函数。这个例子的意义在于展示递归对重复循环进行概括的能力。

创建递归函数时,通常有三个主要结构需要考虑:边界条件、递归前进阶段和递归返回阶段。

边界条件指停止递归的条件。如果没有边界条件,递归可能无限循环地自我调用,如上例。边界条件语句一般根据函数的参数或者全局变量的值作出判断,如果判断为已经到达递归底层,则使用 return 语句返回上一层递归,否则继续递归。

递归前进阶段,始于边界条件之后,止于自我调用。而递归返回阶段,指自我调用的进程返回后,还需要再执行的代码。一些递归函数没有返回阶段,这主要取决于需实现的具体功能。

在图 1 中,递归的三个结构已经用大括号标记出来了。
递归函数
图 1:递归函数

运行这段程序,输出结果如下:

1
2
3
4
5
1
2
3
4
1
2
3
1
2
1
END
END
END
END
END


在程序主体中调用 recurse 函数时,数据 5 被传给了 recurse 函数中的 n。此时,递归的边界条件并未达到,所以 for 循环输出了从 1 到 n 的所有整数。随后,再次调用自身,并使下一个传入函数的数据值减 1。一直到 n 减少到 0 时,函数达到边界条件,返回上一层并执行返回阶段的代码。由输出结果我们可以看出,代码中的前进阶段全部运行完毕后,递归函数才会来到返回阶段。

需要注意的是,设计递归函数时,边界条件要与递归调用语句相对应。以图 1 中的程序为例,如果 recurse 函数在调用自身的时候,传入下一层递归的数据是 n+1,那么边界条件永远不会判定为真,递归也永远不会停止。

虽说递归方便操作,但由于计算机对每一层递归进行压栈操作,所以过多层的递归容易造成栈溢出,效率也比一般的循环算法低。同时,由于递归重复调用自身,在对程序进行手动调试时也会因为逻辑较为复杂而降低效率。但是,在一些特定的情况下,递归是最适合解决问题的算法。

大部分递归算法是可以用循环结构来解决的,例如:
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

这类递归函数就很容易用循环来完成。
def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

被改写完的函数与原函数实现的功能完全一样,除额外的赋值运算外,基本运算次数没有改变。因此我们可以得出结论,前者递归函数的时间复杂度与后者 for 循环函数相同,都为 O(n)。

但如果递归函数无法被完美地写成 for 循环或者 while 循环结构,就需要细致地分析递归函数的细节和原理。
def feb(n)
    if n <= 1:
        return 1
    else:
        return feb(n - 1) + feb(n - 2)

如上所示的是一个计算斐波那契数列函数。而我们都知道斐波那契数列的公式为:

f (n)=f(n−1)+f(n−2)


因为 return 不计入运算,而判断语句为一次运算,所以假设当输入规模为n时该函数的运行次数为 T(n),通过上面公式我们可以得到:

T (n)=(T(n−1)+1)+(T(n−2)+1)


由于常数不会影响到函数整体的时间复杂度,所以可以被简化为:

T (n)=T(n−1)+T(n−2)


到这一步,我们已经知道当输入规模为n时,斐波那契数列函数时间复杂度的递推公式,而我们只需求出通项公式即可分析出其时间复杂度为,
公式
约为 O(1.618n),简化默认为指数级复杂度 O(2n)。可以看出,该斐波那契数列函数的时间复杂度成指数增长,说明这是一个较为低效的递归函数。