如何推导链表递归搜索算法时间复杂度的递推数学表达式

首先定义*T(n)*为链表长度为n时，search函数最坏场景下的时间开销，我们基于给出的Java实现推导：

边界条件 #

当链表长度n=0（即入参head == null）时，仅执行1次判空操作就直接返回，所有操作都是常数时间，记为常数C₀，因此：

T(0) = C₀

递推关系 #

最坏场景为搜索的整数x不在链表中，或x在链表最后一个节点，此时当前节点必然不满足head.data == x的判断，会执行以下操作：

• 2次条件判断（判空、判节点值相等）
• 递归调用子链表的搜索逻辑，子链表长度为n-1，时间开销为T(n-1)
• 对递归返回值做1次判断后返回结果
  以上非递归操作的总耗时为常数C，和n的大小无关，因此得到递推方程：

T(n) = T(n-1) + C （n≥1）

递推式展开求解 #

把递推式逐层展开：

T(n) = T(n-1) + C
= T(n-2) + C + C = T(n-2) + 2C
= T(n-3) + 3C
...
= T(0) + n*C

代入边界条件T(0)=C₀，最终得到T(n) = C*n + C₀，其中C和C₀都是常数，因此最坏时间复杂度为O(n)。

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