如何从算法中找到递归关系

Question

我正在尝试了解递归关系。我找到了一种通过递归确定整数数组中最大元素的方法。下面是函数。第一次调用时，n 是数组的大小。

int ArrayMax(int array[], int n) {
    if(n == 1)
        return array[0];
    int result = ArrayMax(array, n-1);
    if(array[n-1] > result)
        return array[n-1];
    else
        return result;
}

现在我想了解递归关系以及如何从那里获得大 O 表示法。我知道 T(n) = aT(n/b) + f(n)，但我不知道如何得到 a 和 b 应该是什么。

Answer 1

a 是 "how many recursive calls there are"，b 是 "how many pieces you split the data into"，直观上。请注意，递归调用中的参数不必 n 除以某些东西，通常它是 n 的任何函数， 描述了数据的大小如何变化.

比如二分查找在每一层做一次递归调用，将数据分成2份，每一层做不断的工作，所以它有T(n) = T(n/2) + c。合并排序每次将数据一分为二（拆分工作与 n 成正比）并在 both 子数组上递归 - 所以你得到 T(n) = 2T(n/2) + cn.

在您的示例中，您将有 T(n) = T(n-1) + c，因为您正在进行一次递归调用，并且 "splitting the data" 每次将其大小减少 1。

要从中获得大 O 符号，您只需进行替换或扩展。用你的例子很简单：

T(n) = T(n-1) + c = T(n-2) + 2c = T(n-3) + 3c = ... = T(0) + nc

如果你假设 T(0) = c0，一些 "base constant"，那么你会得到 T(n) = nc + c0，这意味着完成的工作在 O(n).

二分搜索示例类似，但您必须进行替换 - 尝试让 n = 2^m，看看您能从哪里得到它。最后，导出例如的大 O 符号。 T(n) = T(sqrt(n)) + c 是一项非常酷的练习。

编辑：还有其他方法可以解决递归关系 - Master Theorem 是一种标准方法。但是证明并不是特别好，并且上述方法适用于我曾经应用过的每次重复。而且...好吧，这比将值插入公式更有趣。

Answer 2

在你的例子中递归关系是：

T(n) = T(n-1) + constant

大师定理说：

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

这里无法应用Master theorem 因为对于master theorem b 应大于 1 (b>1) 在你的情况下 b=1

如何从算法中找到递归关系

how to find a recurrence relation from algorithm

c++

recursion

big-o

recurrence