链表搜索时间复杂度的数学递归方程

Question

如何为使用递归在链表中搜索整数 x 的 'time complexity' 制定数学方程式。递归方程显然应该以 n 为单位（其中 n = 链表中元素的总数）。下面是链表中递归搜索的Java实现。

public static int search(Node head, int x) {
  if(head==null)
    return -1;
  else if(head.data==x)
     return 1;
  else {
     int res=search(head.next,x);
     if(res==-1)
        return -1;
     else 
        return res+1;
  }
}

我知道时间复杂度显然是 O(n)，因为它在最坏的情况下遍历每个元素进行搜索，但我想从递归方程中得出相同的结果。

Answer 1

定义 _, 作为执行搜索的时间复杂度，当具有目标数据的第一个节点位于具有节点的列表中的位置（从 1 开始）时。为了在没有匹配时获得有用的值，让我们定义为列表中最长前缀中没有匹配节点的节点数，...加 1。所以当没有匹配时，我们将有= + 1.

然后：

_{1, 0} 表示空列表的情况，其中（显然）没有这样的节点。
_1,表示头节点有目标数据的情况

然后我们有这些等式：

_{1, 0} = O(1)
_{1，当 > 0
时，} = O(1) _, = O(1) + _{−1, −1} 当 > 1 且 > 0

最后一个等式反映递归调用是用 head.next 进行的：该调用处理的列表比短一个节点，因此涉及的 size ()和匹配position()少一个

首先启动哪个基本案例取决于如何关联。如果 = + 1，则第一个基本案例将启动。在所有其他情况下，第二个基本案例将启动。

递归关系将因此解析为：

_, = O() 当 <=
_, = O(1 + ) 当 = + 1

所以在这两种情况下：

_, = O()

...在最坏的情况下是 O(1 + ) = O()。

链表搜索时间复杂度的数学递归方程

Mathematical Recursive Equation for Time complexity of Linked list Search

algorithm

recursion

search

linked-list

time-complexity