如何计算给定算法的T(n)？附Python搜索函数代码实例

计算T(n)的核心逻辑很简单：统计算法在给定输入规模n下，需要执行的常数级基本操作总次数。常数级操作指单次赋值、等值比较、索引取值、算术运算这类耗时不随输入规模变化的操作，统计完成后按大O表示法规则（忽略常数系数、忽略低阶项）化简，就能得到最终的时间复杂度结果。

你给出的代码如下，我们逐段拆解计算：

import math
def search(k, lst_1, lst_2):
   n = len(lst_1) + len(lst_2)
   
   for i in range(0, math.ceil(n/2)):
       if lst_1[i] == k:
          return 2 * i

   for j in range(0, math.floor(n/2)):
       if lst_2[j] == k:
          return 2 * i + 1

   return -1

步骤1：确定输入规模n #

代码第一行明确定义n = len(lst_1) + len(lst_2)，两个输入列表的总长度就是输入规模，后续所有循环的执行次数都和这个n直接绑定。

步骤2：逐段统计操作执行次数 #

• 初始化n的操作：Python中列表取长度len()是底层实现的常数时间操作，加法、赋值也都是常数时间，这部分总耗时是和n无关的固定常数，记为c1。
• 第一个for循环：循环边界是math.ceil(n/2)，最多执行⌈n/2⌉次。每次循环内部只做两次常数操作：列表索引取值、等值比较；如果匹配到目标值k，执行一次算术运算后直接返回，返回操作也是常数时间。
  • 最好场景：i=0时就匹配到lst_1[0]等于k，这个循环仅执行1次就结束。
  • 最坏场景：lst_1中完全不存在k，这个循环会跑满⌈n/2⌉次，才会进入下一段逻辑。
• 第二个for循环：循环边界是math.floor(n/2)，最多执行⌊n/2⌋次，每次循环内部的操作和第一个循环完全一致，都是常数时间。
  • 承接最坏场景：如果lst_2中也不存在k，这个循环会跑满⌊n/2⌋次，最后执行return -1的常数操作。

步骤3：合并计算总T(n) #

我们通常默认计算最坏场景下的T(n)（这也是时间复杂度分析的通用标准）：
第一个循环跑满⌈n/2⌉次，第二个循环跑满⌊n/2⌋次，两者相加总循环次数为⌈n/2⌉ + ⌊n/2⌋ = n次。每次循环的操作都是常数时间，乘以固定系数c，再加上开头初始化、最后返回的固定常数耗时d，总T(n) = c*n + d。

两个容易混淆的注意点：

• 顺序执行的循环，执行次数是相加关系，只有嵌套循环的执行次数才是相乘关系，不要看到多个循环就误判为平方级复杂度。
• 这段代码第二个循环返回时引用的i是第一个循环执行完的最终值，属于代码逻辑细节，取值操作是常数时间，完全不影响时间复杂度计算。

步骤4：化简得到大O复杂度 #

大O表示法只保留和n相关的最高阶项，忽略所有常数系数、固定常数项，因此这个算法的最坏时间复杂度为O(n)。
补充其他场景的复杂度结果：

• 最好时间复杂度：k出现在lst_1的第一个位置，总操作数为固定常数，对应O(1)
• 平均时间复杂度：假设k等概率出现在两个列表的任意位置，平均需要遍历n/2个元素，依然是线性复杂度，对应O(n)

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