递归查找大 O 时间复杂度

Question

我正在学习时间复杂度，我正在尝试找出一种关系。我的讲义将递归查找函数描述为：

find(array A, item I)
  if(arrayEmpty(A)) return BAD;
  if(item == A[0]) return GOOD;
  return find(allButFirst(A), I);

有用 link : https://www.youtube.com/watch?v=_cG5KZSn1LE

我的笔记说时间复杂度的起始关系如下：

T(n) = 1 + T(n-1) // I understand this
T(1) = 1 // only one computation, understandable

然后我们展开 T(n)

T(N) = 1 + 1 + T(n-2) // every recursive step 1 comparison plus recursive call
T(N) = 1 + 1 + 1 + T(n-3) 
T(N) = 1 + 1 + 1 + 1 + T(n-4) 
...
T(N) = (n - 1) + T(n-(n-1)) // This point I am lost how they got this generalisation

如果有人可以解释上述关系是如何推广到 T(N) = (n - 1) + T(n-(n-1)) 并且为了清楚起见，也许用一个例子会更好。

例如，我想用一些值尝试上述关系，所以假设 A {1, 2, 3} 和 I = 3

那么下面是计算

1 + T(n-1) // {2,3}
1 + 1 + T(n-2) // {3}
1 // {3} Found

所以对于上面我们总共有 3 次比较和 2 次递归调用。所以我会说关系是 T(n) = n + t(n-(n-1)) = n + t(1) = n.

Answer 1

在展开模式的每一步中，如果我们进入递归k步（第一步，k=1，最后一步，k=n），有k 1 个。

在您发布的扩展中，最后一行 T(N) = (n - 1) + T(n-(n-1)) 是倒数第二步，因为 T(n-(n-1)) 扩展为 T(1)，因此对于该行，k=n-1.

因此该行中有 n-1 个 1，因此有 (n-1) 个术语。

同样，在第 k 步传递给 T 的参数是 n 减去当前步数，因为它是剩余的步数。第一行是 n-k = n-1，因此是 T(n-1)。对于倒数第二个步骤，它是 n-k = n-(n-1)，因此 T(n-(n-1)) = T(1)。

递归查找大 O 时间复杂度

Recursive Find Big O time complexity

algorithm

recursion

big-o

time-complexity