基于O-notation求解两段Python代码最坏运行时间紧界咨询

sums1 函数分析 #

你判断的O(n²)是错误的，该函数最紧时间复杂度为O(n)：
你产生误判的原因大概率是对列表拼接的复杂度认知有误，Python中列表拼接a + b的时间复杂度是O(len(a)+len(b))，只会把两个列表的元素依次复制到新内存空间，不会产生平方级开销。
逐行拆解开销：

• 两次filter操作分别遍历完整的列表L，每次遍历开销O(n)，两次总开销O(n)
• 两次list()转换将filter返回的迭代器转为列表，转换的元素总个数等于原列表L的长度n，总开销O(n)
• 最终even + odd拼接的两个子列表总长度为n，开销O(n)
  所有步骤总开销为线性级，因此最紧上界为O(n)。

sums2 函数分析 #

你判断的O(2ⁿ)是正确的，该函数最紧时间复杂度为O(2ⁿ)，推导如下：

• 每次非终止的函数调用首先执行sum(L)，对当前长度为k的列表求和，开销为O(k)
• 随后会产生两个递归分支，分别传入长度为k-1和k-2的列表切片，递归调用的数量随原列表长度n呈斐波那契式指数增长
• 即使叠加每次求和的线性开销，整体增长量级仍然符合指数级，在你给出的可选界中O(2ⁿ)是最紧的上界

补充：常见Python列表操作时间复杂度参考 #

• 遍历类操作（filter、sum、循环迭代、list转换迭代器）：O(k)，k为遍历的元素总数
• 列表拼接a + b：O(len(a) + len(b))
• 列表切片L[x:y]：O(y - x)，即切片返回的元素个数

内容的提问来源于stack exchange，提问作者user16427705