列表大小翻倍的竞争性

Question

我不明白为什么res=res+res的复杂性是O（n）。在该代码中，res在每次迭代中都会将其大小加倍，因此该行的复杂性会随着每次迭代而变化，如下所示：

2+4+8+…+n=O（n）

我不明白为什么这个级数等于O（n）

def ones (n): # complexity O(n)
    res = [1] # 1 = O (1)
    while len ( res ) < n: # 1 + 1 ... + 1 ( log n times ) = O(log n)
        res = res + res # 2 + 4 ... + n = O(n) Why this is O(n)
    return res # 0 = O (0)

Answer 1

将列表的大小加倍的复杂性永远不会大于N，但是，由于在循环中重复logN次，因此函数的总体复杂性将为O(NlogN)

我宁愿推荐线性解决方案，如：

def ones(n) :
    return [1] * n