python - 时间复杂度:嵌套for循环中的列表不断增加

在此代码中：

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

该算法的Big O为3 ^ n * n。我对吗？

最佳答案

只是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)

关于python - 时间复杂度:嵌套for循环中的列表不断增加，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55196756/