难以理解函数的运行时复杂性
Trouble understanding the runtime complexitiy of a function
我正在备考，题目如下；给定函数：
def foo(lst):
count = 0
while len(lst)>1:
mid = len(lst)//2
lst = lst[:mid]
count += lst[-1]
return count
它的运行时间复杂度是多少？
据我了解，由于列表每次都被减半，因此外部 while 循环将 运行 logn 次。切片是一个 O(n) activity，因此，运行时间将是 nlogn。不幸的是，答案声称 运行 时间是 O(n)。我哪里错了？
简答：对列表进行切片在 O(n) 中运行，但由于列表每次都被切成两半，所以意味着第二次迭代中的 n 是前一次迭代的一半。
如果切片到 k 正好需要 k "instructions"，那么这意味着算法归结为n/2 + n/4 + n/8 + ... + 1，或者更正式一点：
log n
--- n
\ ---
/ i
--- 2
i=1
上面是一个geometric serie [wiki]等于：
n/2 n/2
------- - 1 = --- - 1 = n - 1
1 - 1/2 1/2
所以指令总数为O(n).
我正在备考，题目如下；给定函数：
def foo(lst):
count = 0
while len(lst)>1:
mid = len(lst)//2
lst = lst[:mid]
count += lst[-1]
return count
它的运行时间复杂度是多少？
据我了解，由于列表每次都被减半，因此外部 while 循环将 运行 logn 次。切片是一个 O(n) activity，因此，运行时间将是 nlogn。不幸的是，答案声称 运行 时间是 O(n)。我哪里错了？
简答：对列表进行切片在 O(n) 中运行，但由于列表每次都被切成两半，所以意味着第二次迭代中的 n 是前一次迭代的一半。
如果切片到 k 正好需要 k "instructions"，那么这意味着算法归结为n/2 + n/4 + n/8 + ... + 1，或者更正式一点：
log n
--- n
\ ---
/ i
--- 2
i=1
上面是一个geometric serie [wiki]等于：
n/2 n/2
------- - 1 = --- - 1 = n - 1
1 - 1/2 1/2
所以指令总数为O(n).