算法的递归关系

Question

我已经给出了下面的算法，我必须找到递归关系。

int Recursive(int n)
{
   if(n<=1)
     return n;
   sum=0;
   for(int j=0;j<n;j++)
      sum++;
   return Recursive(n/2) + Recursive(n/2) + sum;
}

我已经得到上述算法的递归关系

T(n) = 2 T(n/2) + constant

但是我不确定这个递归关系的常数部分，因为我们在算法中有 sum。澄清一下，sum 是一个全局变量 - 缺少声明是 而不是 拼写错误。

任何人都可以帮我得到正确的递推关系吗？谢谢

Answer 1

I am not sure about the constant part of this recurrence relation

没有常数部分，因为循环后sum等于n。这给出：

T(n) = 2T(n/2)+n

So if the sum is global variable, T(n) = 2T(n/2)+C(Constant) and if sum is local variable T(n) = 2T(n/2)+n . Am I correct?

不，正如 mch 所写：

It seems that sum is a global variable… In this case it would be unspecified if sum or one of the Recursive(n/2) will be evaluated first.

这意味着 未指定 无论是 T(n) = 2T(n/2)+n 还是 T(n) = 2T(n/2)+n/2；在这两种情况下都没有常数部分。

Answer 2

此答案中的假设：

sum 是全局声明的——因为正如您所说，显然缺少的声明不是拼写错误。
问题要求 return 值，而不是时间复杂度。
return 语句中的表达式按它们出现的顺序求值； C 标准不保证这一点，所以答案在技术上是未定义的。

请注意，由于每次调用都会执行以下任一操作：

Returns 它的参数 (if n <= 1)
将 sum 的值重置为 0

... 函数保证为 "closed"，因为它的 return 值仅取决于它的参数。由此可见：

The two separate calls to Recursive(n / 2) can be combined into just one call, without impacting the return value: return 2 * Recursive(n / 2) + sum;.

从这一点开始，假定此修改已应用于原始代码；这有助于阐明程序的流程，因为现在只有一个执行路径（而不是由两次调用创建的分支）。

现在进入关键部分。对 Recursive(n / 2) 的调用覆盖 函数 return 之前 sum 的值，撤消前面 for- 所做的工作环形。这种覆盖行为在递归层次结构中继续向下，直到当停止条件n <= 1被命中时的最终调用（它只是returns n） .由此可见：

There is only one value of sum which contributes to the final return value, given by its value after the penultimate call to Recursive.

由于整数除法截断，当执行倒数第二个调用时n总是2或3（均满足n / 2 = 1）；因此，这些也是 sum.

可能的最终值

n 的什么值分别给出 sum = 2 和 sum = 3？考虑 n 的二进制表示是说明性的。

整数除以 2 相当于将位模式 "right" 移动 1（或 "left"，具体取决于字节顺序......），并丢弃最低有效位。因此，sum 的最终值仅取决于 2 个最高有效位 n:

 initial bit-pattern  >>  penultimate call
 -----------------------------------------
 ...000 10 xxx...         ...0000 10 = 2       
 ...000 11 xxx...         ...0000 11 = 3

 xxx: discarded bits

n 的位模式有 floor(log2(n)) + 1 个有效位；因此，sum 的最终值可以简洁地表示为：

S(n) = 2 + second_most_significant_bit(n)

sum 与 return 值相加了多少次？递归调用Recursive的次数（即调用总数减一，包括初始调用，但不包括最终调用）。这是由 floor(log2(n)):

给出的

请注意，如果最初 n >= 1，最终调用的 return 值将始终为 1。因此，Recursive 的最终 return 值由下式给出：

测试C代码确认：

// override the library definition of log2 to use integers only
int log2(int n) {
   int b = 0;
   while ((n >>= 1) != 0)
      b++;
   return b;
}

// get i-th bit from bit pattern of n
int get_bit(int n, int i) {
   return (n >> (i - 1)) & 1;
}

// calculating return value of Recursive using equation above
int Value(int n) {
   int l2n = log2(n);    // floor(log2(n))
   int p2l = 1 << l2n;   // 2^(floor(log2(n)))
   return p2l + (p2l - 1) * (2 + get_bit(n, l2n));
}

结果：

n        | Recursive    Value
-------------------------------
2        |  4           4
3        |  5           5
4 - 5    |  10          10
6 - 7    |  13          13
8 - 11   |  22          22
12 - 15  |  29          29
16 - 23  |  46          46
24 - 31  |  61          61
32 - 47  |  94          94
48 - 63  |  125         125
64 - 95  |  190         190

算法的递归关系

Recurrence relation for the algorithm

c

algorithm

recursion

recurrence