Сложность времени: растущий список во вложенных циклах

Question

В этом коде:

test = [1] * 10
result = []
for i in test:
    if not result:
        result = [i,i,i]
    else:
        new_result = []
        for j in result:
            for k in range(3):
                new_result.append(i + k)
        result = new_result

Внешний цикл выполняется n раз.Внутренний цикл, если я не ошибаюсь, запускается 3 ^ n

Большой O этого алгоритма - 3 ^ n * n.Я прав?

Answer 1

Это просто 3^n.если вы попробуете это после выполнения:

print(len(result)) #result: 59049
print(3**len(test)) #result: 59049

Так что да, оно растет в геометрической прогрессии относительно размера n, так как вывод result будет расти следующим образом на каждой итерации:

3
9
27
81
243
729
2187
6561
19683
59049

Я использовал timeit, чтобы распечатать время выполнения при увеличении n

n = 10 # Time:  0.020012678000000002
n = 11 # Time:  0.057932331000000004
n = 12 # Time:  0.15807880600000002

Вы видите, куда оно идет с точки зрения времени.

вот код, который я использовал:

import timeit
test = [1] * 12
result = []
start = timeit.default_timer()

print(test)
for i in test:
    if not result:
        result = [i,i,i]
        print(result)
    else:
        new_result = []
        print(len(result))
        for j in result:
            for k in range(3):
                new_result.append(i + k)
        result = new_result

stop = timeit.default_timer()

print('Time: ', stop - start)