麻烦了解功能的运行时复杂性

Question

我目前正在学习考试，问题如下；给定功能：

def foo(lst):
   count = 0
   while len(lst)>1:
       mid = len(lst)//2
       lst = lst[:mid]
       count += lst[-1]
   return count

它的运行时复杂性是什么？

对我的理解，由于列表每次切成两半，循环的外部循环将运行logn次。切片是O(n(活动，因此，运行时为nlogn。不幸的是，答案声称运行时为O(n(。我在哪里做错了？

Answer 1

简短答案：切片列表以 o(n(运行，但是由于列表每次切成两半，表示第二次迭代中的 n 是前一个迭代的一半。

如果将切片切成 k 完全采用 k "指令"，那么这意味着算法归结为 n/2 n/4的总和 N/8 ... 1 或更正式：

log n
---     n
      ---
/        i
---     2
i=1

以上是A 几何serie [Wiki]等于：

  n/2         n/2
------- - 1 = --- - 1 = n - 1
1 - 1/2       1/2

因此，指令总数为 o(n(。