需要 2 个参数的递归递归公式

Question

我可以根据递归创建一个递归公式，它只传递一个参数（类似于 $T(n/2)$）。但是，对于这种 $u$ 和 $v$ 的值不同的情况，我该如何将它们放在一起呢？这是问题所在：

对某个 n > 2 的递归函数 RecursiveFunction(n, n) 的调用

RecursiveFunction(a, b) 
if a >= 2 and b >= 2
   u=a/2
   v=b-1
   RecursiveFunction(u, v)

最终目标是找到最坏情况 运行 时间的紧渐近边界，但我首先需要一个公式。

Answer 1

根据 a 和 b 的相对大小，实际上有两个不同的答案。

函数可以这样写：

其中 C 是每次调用完成的一些恒定工作（if 语句，将 u, v 压入调用堆栈等）。由于两个变量独立演化，我们可以分别分析它们的演化

1. a - 考虑以下函数：

   将迭代案例扩展 m 次：

   停止条件a < 2是这样的：

2. b - 和以前一样：

因此，T(a, b) 的复杂性取决于哪个变量首先达到其停止条件，即 m 和 n 之间的最小变量：