循环的时间复杂度 [英] time complexity for a loop

问题描述

foo = []
i = 1
while i < n:
    foo= foo + ["a"]
    i*=2

这段代码的时间复杂度是多少？

我的想法是：
while循环记录log（n）迭代。对于每个迭代，都会创建一个新列表。

因此，总时间复杂度为：O（log ^ 2（n））。

What is the time complexity of this code?
My thoguht is: the while loop does log(n) iteration. For each iteration new list is created.
So, the total time complexity is: O(log^2(n)).

我正确吗？

推荐答案

while 循环迭代log（n）次。

The while loop iterates log(n) times.

foo + [ a] ：通过复制原始列表来创建新列表。根据时间复杂度-Python Wiki ，复制列表为O（n）。

foo + ["a"]: Create a new list by copying the original list. According to Time Complexity - Python Wiki, copying a list take O(n).

时间复杂度
=> 1 + 2 + 3 + ... + log（n）
=>（log（n）+1）*对数（n）/ 2
=> O（log ² n）

我运行了 timeit ：（ CPython 2.7.5 64位，Windows 7）

I ran a timeit: (CPython 2.7.5 64bit, Windows 7)

def f(n):
    foo = []
    i = 1
    while i < n:
        foo = foo + ["a"]
        i *= 2

import timeit
for n in range(20):
    print n, timeit.timeit('f({})'.format(2 ** n), 'from __main__ import f')

结果：

2**0 0.187083903003
2**1 0.455513095565
2**2 0.690063737582
2**3 0.925251130713
2**4 1.16173567555
2**5 1.38232866174
2**6 1.64922777752
2**7 1.89248633685
2**8 2.14087549485
2**9 2.36934465058
2**10 2.62737119511
2**11 2.91843160213
2**12 3.19988987374
2**13 3.43422677799
2**14 3.72119850214
2**15 4.00189195846
2**16 4.31630377356
2**17 4.62789416099
2**18 4.91062905834
2**19 5.24480246883

这篇关于循环的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！