一个循环的时间复杂度

Question

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

这段代码的时间复杂度是多少？
我的思路是： while循环执行log（n）迭代。对于每次迭代，创建新列表。
所以，总的时间复杂度是：O（log^2（n））。

我对不对？

Answer 1

该循环执行log（n）次迭代。

现在，假设foo = foo + ["a"]立即复制foo中的每个元素以进行级联（而不是一些奇特的列表附加），那么对于每次迭代，最多也有log(n)拷贝。

所以，是的，它是log(n)*log(n) = log^2(n)

Answer 2

的while循环迭代的log（n）次。

foo + ["a"]：通过复制原始列表来创建新列表。根据Time Complexity - Python Wiki，复制一个列表需要O（n）。

时间复杂度 => 1 + 2 + 3 + ... +的log（n） =>（的log（n）+ 1）*的log（n）/ 2 =>为O（log 2 N）

---

我跑了timeit：（CPython的2.7.5 64位，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 

Answer 3

假设循环迭代Ñ代替日志（Ñ）次，然后在阵列复制取0 + 1 + 2 + 3 + 4个+ ... + Ñ -2操作;并用Ñ 2花费

0 + 1 + 2 + 3 + 4 + ... + Ñ = 1/2·Ñ·（Ñ 1）

操作。为简单起见，让我们取代Ñ 2由米，所以Ñ 2 =米，从而Ñ =米 -2和

二分之一·Ñ·（ñ 1）= 1/2·（米 -2）·（米 -2 + 1）= 1/2·（米 -2）·（米 -1），

我们将使用以后作为

F（米）= 1/2·（米 -2）·（米 -1）。

现在，作为循环的限制不是Ñ 2但登录（Ñ），没有

F（Ñ 2）= 1/2·（（ ñ 2）-2）·（（ñ 2）-1）= 1/2·ñ·（ñ 1）（见上文发散系列）

但

F（日志（Ñ））= 1/2·（日志（Ñ）-2）·（日志（Ñ）-1）

操作，这是

二分之一·（日志（ñ）-3·log（n）+2）ε0（log （n））。 ■