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

Question

我设计了一个算法，但不知道时间复杂度是θ（n）还是θ（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）？你知道吗

Answer 1

假定insert方法不会移动数组，也就是说，对于算法，它只在列表末尾附加一个元素，即时间 复杂性是O(1)。此外，访问带有索引的元素也需要O(1)时间。你知道吗

在循环中运行number次的次数是O(1)秒。O(number)*someO(1)s = O(number)

Answer 2

list.insert的复杂性是O（n），如this wiki page所示。您可以检查^{}库，它提供了一个具有O（logn）插入的优化列表类型，但是在您的算法中，我认为该项总是放在数组的末尾，因此它只是一个append，需要固定的摊销时间（您可以用append替换insert，以使代码更优雅）。你知道吗

Answer 3

对于任意大的数，情况并非如此，因为两个大数相加需要对数时间来计算这些数的值。如果我们假设总和不会失控，那么我们可以说它是在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))

因此，我们不需要使用其他列表，因为我们只对最后一项感兴趣。你知道吗