我正试图把我的头裹在空间里&算法的时间复杂性。
我有两个例子，说明修改数组中每个单独元素的不同方法。我正在使用Python，我很好奇这两个操作的复杂性之间是否有区别。。。
首先，我用Python初始化一个列表，对该列表进行迭代，并将列表中每个元素的1+I之和附加到已经初始化的新列表中。
# initialize f
f = [1.2, 2.5, 2.7, 2.8, 3.9, 4.2]
# initialize new list new_f
new_f = []
# loop through f and add each modified element to the new list
for i in f:
new_f.append(1+i)
print(f"new_f = {new_f}")
第二种方法包括创建一个numpy数组，我们将称之为na，然后简单地向每个元素添加1，如下所示：
# import scientific computing package NumPy
import numpy as np
# create new array "na"
na = np.array([1,2,3,4,5])
# add 1 to each element in na
na = na + 1
print(na)
我真的不相信我在这一点上完全理解Big-O表示法，但在我看来，这两种方法的时间复杂性都是O(n(。然而，第一种方法的空间复杂度为O(n+m((或者，可能为O(2n(？(因为正在创建一个新的列表，而numpy方法的空间复杂度只有O(n(，因为原始的np数组将被破坏。
有人能帮我验证我的逻辑是否正确，或者澄清一下吗？提前感谢！！
因此，首先，na = na + 1也需要额外的空间；您正在创建一个具有递增值的新数组，并替换原始数组，在创建新数组时，原始数组仍然存在，因此您的峰值内存使用率会翻倍，就像在非numpy的情况下一样。为了避免这种成本，您必须编写na += 1，它将委托给就地添加代码。
另一个需要注意的更正是，如果包含最初占用的空间，则此代码的所有版本都具有O(n)空间复杂性。常量因子在big-O表示法中被忽略，因此即使您复制并将内存使用量增加一倍，所需的空间仍然是O(n)。这意味着它与n成比例；它实际上可以是每个元素1GB，并且它仍然是CCD_；如果您碰巧将使用的内存增加了一倍，但它仍然与n严格成比例，那么它仍然是O(n)。如果您只谈论所需的额外空间，则就地解决方案可以描述为O(1)，而非就地解决方案则为O(n)，仅此而已。