python - while 循环的时间复杂度

Question

我完全不确定我是否理解时间复杂度的计算。我得到了这些循环，这些是我的计算。但是，对于这里的大 O，我完全不确定该说些什么。

循环 1:

lst = []                   
i=1                        
while i<n:
  lst = list(range(i))       
  i *= 2 

我假设每个操作都需要 O(1) 时间。在这个循环中，第 1 行和第 2 行各执行 1 次。 while 循环的第一行有 3 个操作——范围、列表和将该值赋给 lst。由于我们处理的是范围，我假设它运行了 n+1 次。

循环的最后一行有 2 个操作:乘以 2 并将该值赋给 i，它运行 n 次。

据此，我认为总数将是: 1+1+3(n+1)+2n = 5n+5。

既然这是一个线性函数，那么大O就是O(n)？

===============

循环 2:

lst = []            
i=1                 
while i<n:
  lst = lst + [i]      
  i *= 2    

这里我们有一个类似的例子，但是 while 循环的第一行有 2 个操作。 然后，
1+1+2n+2n = 4n+2。

既然是线性函数，那也是O(n)吗？

========================== 循环 3:

lst = []          
i=1                
while i<n:
  lst += [i]         
  i *= 2  

我认为 lst +=[i] 会执行 2n 次 2 次操作，因为这是就地计算？我不确定这一点。如果这是正确的，那么总数将是 6n+2

问题是:我的计算是正确的还是完全错误的？如何为每个循环编写大 O？

Answer 1

循环 1:O(n log n)

循环运行 log2(n) 次，平均 O(log n)。每次迭代(在最坏的情况下)执行 n 个操作。所以复杂度是 O(n log n)。

循环 2:O(log n)

循环运行 log2(n) 次，平均 O(log n)。 我想赋值 lst = lst + [i] 只是添加节点(而不是创建新列表)。它的平均值为 O(1)，因此复杂度为 O(log n)。 如果我错了，赋值会创建新列表，因此每次迭代都会(在最坏的情况下)执行 n 个操作。所以复杂度是O(n log n)

循环 3:O(log n)

在循环 2 中，这里的赋值肯定是 O(1)，而不是假设...