与多参数函数的递推关系

Question

我一直在努力思考递归关系的概念，并且了解了如何划分、征服和组合。我无法理解的是如何从处理值数组、最低索引和最高索引的多参数函数中导出正确的递归关系。

更多背景信息：我的基本情况是最低索引等于最高索引。当满足该条件时，我 return 从最低索引开始的元素。（也是最高的）是唯一的元素。

我的递归情况是 q 和 p 不相等。这是下面的代码：

int maximum(int[] A, int p, int q) {
 if (p == q) {
   return A[p];
 }
 int k, l, max1, max2, max3;
 k = p + Math.floor((q-p+2)/3);
 l = k + Math.floor((q-p+2)/3);
 max1 = maximum(A, p, k-1);
 max2 = maximum(A, k, l-1);
 max3 = maximum(A, l, q);
 if (max1 >= max2 && max1 >= max3) {
   return max1;
 } else if (max2 >= max1 && max2 >= max3) {
  return max2;
 } else {
   return max3;
 }
}

我不确定我会怎么做。从我见过的每个例子来看，我应该使用 n 作为我的输入大小，我唯一关心的参数是我的输入大小。

有人能解释解决几乎所有算法的最佳方法吗？我觉得这种特殊类型很适合我，因为我习惯于在递归关系背后的解释中看到更简单的递归函数。

Answer 1

在这种情况下，我看到函数的输入大小被认为不是文字输入大小（在每次递归调用时可能或多或少保持相同），而是被考虑的数据的有效大小.在你的算法中——很像合并排序——所考虑的数据的有效大小在每次递归调用时都会缩小：你的高索引和低索引绑定了你正在查看的数组部分，所以在某种意义上你的有效输入大小确实收缩。因此，与其将此类情况视为多变量递归，不如将递归视为 T(n) = 3T(n/3) + O(1) 或类似性质的递归。

现在，有些函数具有多个自变量是有意义的......例如，一个函数接受两个数组并以不同的速率缩小范围。图算法通常（但不总是）将顶点和边视为复杂性边界的独立变量，作为一个具体案例。在这些情况下，自变量被认为是真正独立变化的，不能有意义地组合成有效规模的单一衡量标准。在你的函数中不一定是这种情况。

与多参数函数的递推关系

Recurrence Relations with Multiparameter Functions

java

recursion

discrete-mathematics

recurrence