python - 时间复杂度: growing list in nested for-loops

标签 python time-complexity big-o

在此代码中:

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。我对吗?

最佳答案

只是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 - 时间复杂度: growing list in nested for-loops,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55196756/

相关文章:

python - LSTM 自动编码器的可变长度输入 - Keras

algorithm - 递归复杂,答案错了?

algorithm - 如何在线性计时器中对数组进行排序?

java - 证明 Big-Oh 表示法

python - 使用 Python 重新组装以 'message/partial' 编码的电子邮件消息

python - 将1D字节对象 reshape 为3D numpy数组

python - 将 pandas 数据框转换为具有新键名的字典

c++ - 我的堆排序算法时间复杂度分析是否正确?

arraylist - 是否可以创建一个具有 log(n) 复杂度的 ArrayList 属性的 Map?

Python:查找句子的所有字谜