foo = []
i = 1
while i < n:
foo= foo + ["a"]
i*=2
Какова временная сложность этого кода?
Мое мнение таково: цикл while регистрирует (n) итерацию. Для каждой итерации создается новый список.
Таким образом, общая временная сложность составляет: O(log^2(n)).
Я прав?
Цикл while повторяется log(n) раз.
foo + ["a"]: Создайте новый список, скопировав исходный список. Согласно Time Complexity — Python Wiki, копирование списка занимает O(n).
Временная сложность => 1 + 2 + 3 + ... + log(n) => (log(n) + 1) * log(n) / 2 => O(log2n)
Я запустил 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
Цикл регистрирует (n) итераций.
Теперь, предполагая, что foo = foo + ["a"] немедленно копирует каждый элемент в foo, чтобы выполнить конкатенацию (в отличие от какого-то причудливого добавления списка), тогда для каждой итерации также будет не более log(n) копий.
Так что да, это log(n)*log(n) = log^2(n)
+ делает копию двух списков в один новый, он никоим образом не изменяет исходные экземпляры.
- person Lasse V. Karlsen; 23.11.2013
Предположим, что цикл выполняет n вместо log(n) раз, тогда копирование массива занимает 0+1+2+3+4+…+n< /em>-2 операции; а с n+2 требуется
0+1+2+3+4+…+n = 1/2·n·(n+1)
операции. Для простоты заменим n+2 на m, так что n+2 = m, таким образом, n = m-2 и
1/2·n·(n+1) = 1/2·(m-2)·(m-2+1) = 1/2·(m-2)·(m-1),
который мы будем использовать позже как
f(m) = 1/2·(m-2)·(m-1).
Теперь, поскольку предел цикла равен не n+2, а log(n),
f(n+2) = 1/2·((n+2)-2)·((n+2)-1 ) = 1/2·n·(n+1) (см. расходящиеся ряды выше)
но
f(log(n)) = 1/2·(log(n)-2)·(log(n)-1)
операции, то есть
1/2·(log2(n)-3·log(n)+2) ∈ Ο(log2< /sup>(n)). ■
