这个函数返回的值是多少？

Question

我的老师给我们出了一道非常难的算法课。

让我们考虑下面的代码，其中 random(a) 是一个原语，其中 return 是一个随机整数值，均匀分布在 [0;a] 中，并且具有复杂度 Theta(1)。

  int test(int n)
{
  if(n<=2) return n;
  int i = random(n-2);
  return test(i) + test(n-2-i);
}

对于 n = 9，return 有什么作用；
表达式test(2016)的最小值是多少？
表达式test(2016)的最大值是多少?

我试图概括通用步骤的表达式 k 但我陷入了概率问题，我不知道如何表达它们。这不是作业，只是想一想。

Answer 1

让我们尝试为 i:3..9 计算 test(i) 以了解它可能 return 对于 9
我们有 test(n) = test(i) + test(j)，其中 i+j = n-2，i <= n-2 且 j <= n-2
测试(3)= 测试(1) + 测试(0) = 1
测试（4）=测试（2）+测试（0）||测试(1)+ 测试(1) = 2
测试（5）=测试（3）+测试（0）||测试(2) + 测试(1) = 1 || 3（这里开始问题）
测试（6）=测试（4）+测试（0）||测试（3）+测试（1）||测试（2）+ 测试（2）= 2 || 4
测试（7）=测试（5）+测试（0）||测试（4）+测试（1）||测试（3）+ 测试（2）= 1 || 3
测试（8）=测试（6）+测试（0）||测试（5）+测试（1）||测试（4）+测试（2）||测试（3）+ 测试（3）= 2 || 4
测试（9）=测试（7）+测试（0）||测试（6）+测试（1）||测试（5）+测试（2）||测试（4）+ 测试（3）= 1 || 3 || 5
因此，如果 n%2 =0，test(n) 可能 return 小于 n 的偶数，而在其他情况下（这很酷），小于 n 的偶数
至于最小测试（2016），如果随机总是 return 0 你将有 test（2016）= test（2014）....=test（2）=2
对于最大测试（2016）它是 1008，如果随机总是 return (n-2)/2
事实上，我进行了编辑 test(2016) = 1008
测试（4n）可能 return {2,4,...,2n}
测试（4n+1）可能 return {1,3,...,2n+1}
测试（4n+2）可能 return {2,4,...,2n+2}
测试（4n+3）可能 return {1,3,...,2n+1}
我认为这可以通过归纳来验证，对于 n =1
是正确的 test(4n+4) = test(2) + test(4n) 因为 test(4n) 可能 return = 2n 我们有 test(4n+4) 可能 return 2n + test(2) = 2n +2
因为 test(4n+4) 可能 return test(4n+2) 和 test(4n) => test(4n+4) 可能 return 所有值 return 由 test (4n) => 它可以 return {2,4,... 2n+2}
很明显，test(4n+4) 不能 return 一个偶数，它是两个 test(i) 和 test(j) 的总和，因为 i+j = 4n+4，i 和 j 是两者都是偶数或两者都是偶数，并且根据归纳法的假设，结果是偶数。
最后一步是证明 test(4n+4) 不能大于 2n+2:
test(4n+4) = test(i) + test(j) 其中 i+j = 4n +2，再次使用归纳假设 max(test(i)=< (i/2)+1 和 max(test (j)) <= (j/2)+1
所以 test(4n+4) <= 2n + 3 因为它是偶数 test(4n+4) <= 2n + 2.

这个函数返回的值是多少？

What is the value returned by this function?

algorithm

max

minim