从代码转换为递归关系

Question

我正在准备考试，遇到了一些我需要解决的问题 - 处理基本案例:

我正在从代码转换为递归关系，而不是相反

示例 1:

 if(n==1) return 0;

现在与那段代码的递归关系是:T(1) = 0

我是怎么得到的？
通过查看 n==1，我们看到这是一个值 > 0 的比较，它正在做某种形式的工作，所以我们设置“T(1)”并返回 0；没有做任何工作，所以我们说“=0”

 => T(1) = 0;

示例 2:

 if(n==0) return n+1*2;

分析:n==0 表示我们没有做任何工作，所以 T(0)，但返回 n+1*2；正在工作，所以“=1”

 => T(0) = 1;

我想知道的是，这是否是分析这样一段代码以提出递归关系基本案例的正确方法？

我不确定这些是我自己想出的，以耗尽基本案例的可能性:

Example 3: if(n==m-2) return n-1; //answer: T(1) = 1; ?
Example 4: if(n!=2) return n;     //answer: T(1) = 1; ?
Example 5: if(n/2==0) return 1;   //answer: T(1) = 1; ?
Example 6: if(n<2) return;        //answer: T(1) = 0; ?

Answer 1

很难在代码上下文之外分析基本案例，因此如果您发布整个函数可能会有所帮助。但是，我认为您的困惑是由于假设 T(n) 始终代表“工作”。我猜您正在学习复杂性类(class)，并且您已经了解了递归关系作为表达递归函数复杂性的一种方法。

T(n) 只是一个函数:你插入一个数字 n(通常是一个正整数)，然后你得到一个数字 T(n)。就像任何其他函数一样，T(n) 本身没有任何意义。但是，我们经常使用带有符号 T(n) 的函数来表示算法在大小为 n 的输入上运行所需的时间量。这是两个独立的概念； (1) 函数 T(n) 以及表示它的各种方式，例如递归关系，以及 (2) 运行算法所需的操作数。

让我举个例子。

int factorial(n)
{
   if (n > 0)
       return n*factorial(n-1);
   else
       return 1;
}

让我们看看我们是否可以编写一些表示代码输出的函数 F(n)。好吧，F(n) = n*F(n-1)，其中 F(0) = 1。为什么？从代码中可以清楚地看出，F(0) 的结果是 1。对于任何其他 n 值，结果是 F(n) = n*F(n-1)。这种递归关系是表达递归函数输出的一种非常方便的方式。当然，我可以很容易地说 F(n) = n! (阶乘运算符)，这也是正确的。这是同一函数的非重复表达式。请注意，我没有提及算法的运行时间或它正在做多少“工作”。我只是在为代码输出的内容编写一个数学表达式。

处理函数的运行时间有点棘手，因为您必须确定“工作”或“操作”是什么意思。假设我们不将“返回”算作一个运算，但我们将乘法算作一个运算，并将一个条件(if 语句)算作一个运算。在这些假设下，我们可以尝试为函数 T(n) 编写递推关系，描述当输入 n 给函数时做了多少工作。 (稍后，我将评论为什么这是一个糟糕的问题。)对于 n = 0，我们有一个条件(if 语句)和一个返回，没有别的。所以 T(0) = 1。对于任何其他 n > 0，我们有一个条件，一个乘法，但是需要许多操作来计算 T(n-1)。所以 n 的总和是:

T(n) = 1 (conditional) + 1 (multiply) + T(n-1) = 2 + T(n-1),
T(0) = 1.

我们可以将 T(n) 写成递归关系:T(n) = 2 + T(n-1), T(0) = 1。当然，这也只是函数 T(n) = 1 + 2n .再次，我想强调这是两个非常不同的功能。当 n 是输入时，F(n) 描述函数的输出。 T(n) 描述了当 n 是输入时做了多少工作。

现在，我刚刚描述的 T(n) 在复杂性理论方面是不好的。原因是复杂性理论不是关于描述计算仅以单个整数作为参数的函数需要多少工作。换句话说，我们不是在研究 F(n) 形式的函数所需的工作。我们想要更一般的东西:在大小为 n 的输入上执行算法需要多少工作。例如，MergeSort 是一种用于对对象列表进行排序的算法。它大约需要 nlog(n) 次操作才能在 n 个项目的列表上运行 MergeSort。请注意，MergeSort 没有对数字 n 做任何事情，而是对大小为 n 的列表进行操作。相比之下，我们的阶乘函数 F(n) 并没有对大小为 n 的输入进行操作:大概 n 是一个整数类型，因此它可能是 32 位或 64 位或其他类型，无论其值如何。或者你可以挑剔地说它的大小是描述它的最小位数。在任何情况下，n 都是输入，而不是输入的大小。

当您回答这些问题时，重要的是要非常清楚他们是否需要描述函数输出的递归关系，还是描述函数运行时间的递归关系。