时间戳

首页 > 解决方案 > 我对算法的时间复杂度感到困惑

python - 我对算法的时间复杂度感到困惑

问题描述

我设计了一个算法，但对时间复杂度是 theta(n) 还是 theta (n^2) 感到困惑。

def prefix_soms(number):
    Array_A=[1,2,3,4,5,6]
    Array_B=[]
    soms=0
    for i in range(0,number):
        soms=soms+Array_A[i]
        Array_B.insert(i,soms)
    return Array_B[number-1]

我知道 for 循环正在运行 n 次，所以这是 O(n)。

内部操作是 O(1) 吗？

标签： pythontime-complexity

解决方案

对于任意大数，情况并非如此，因为将两个大数相加需要这些数字的值的对数时间。如果我们假设总和不会失控，那么我们可以说它在O(n)中运行。.insert(…)基本上只是.append(…)一个. 附加n项的摊销成本为O(n)。

然而，我们可以通过这样写来提高可读性和内存使用率：

def prefix_soms(number):
    Array_A=[1,2,3,4,5,6]
    soms=0
    for i in range(0,number):
        soms += Array_A[i]
    return soms

或者：

def prefix_soms(number):
    Array_A=[1,2,3,4,5,6]
    return sum(Array_A[:number])

或者我们可以省略创建列表的副本，使用islice(..)：

from itertools import islice

def prefix_soms(number):
    Array_A=[1,2,3,4,5,6]
    return sum(islice(Array_A, number))

因此我们不需要使用另一个列表，因为我们只对最后一项感兴趣。

推荐阅读