对此代码片段进行严格的大运行时分析

Question

public static long F (int N) {
    if ( N == 1 ) return 1;

    return F(N - F(N-1));
}

现在我认为内部F(N-1)将为每个F(N-F(N-1))执行N次,因此它将是N ^2,但这似乎不是答案.

有人可以告诉我为什么吗？

Answer 1

为了解决这个问题,让我们想象一下以相同的方式重写这段代码:

public static int F (int N) {
    if ( N == 1 ) return 1;
    int k = F(N - 1);
    return F(N - k);
}

我在这里所做的就是拉出内部调用F(N - 1)并将其移至顶层,以便我们可以更清楚地看到此代码进行两次调用F,第二次调用是依赖于第一次调用的子问题.

为了确定这里的运行时间,我们需要弄清楚k是什么,这样我们才能看到我们正在进行什么样的递归调用.有趣的是,事实证明所有N的F(N)= 1.您可以在这里发现这种模式:

• F(1)= 1.
• F(2)= F(2-F(1))= F(2-1)= F(1)= 1
• F(3)= F(3-F(2))= F(3-1)= F(2)= 1
• F(4)= F(4-F(3))= F(4-1)= F(3)= 1

通过归纳证明这一点是一个很好的练习.

所以这意味着对F(N - k)的调用将调用F(N - 1).这意味着代码在功能上等同于

public static int F (int N) {
    if ( N == 1 ) return 1;
    int k = F(N - 1);
    return F(N - 1);
}

这有复发关系

• F(1)= 1
• F(n)= 2F(n-1)+ 1

这解决了F(n)= 2 ⁿ - 1.(同样,如果你愿意,你可以通过归纳正式证明这一点).因此,复杂度为Θ(2 ⁿ).

为了验证这一点,这里是一个(非常hacky)C脚本,它在许多不同的输入上调用函数,报告返回的值和调用的数量:

#include <stdio.h>

/* Slightly modified version of F that tracks the number of calls made          
 * using the second out parameter.                                              
 */
static int F (int N, int* numCalls) {
  /* Track the number of calls. */
  (*numCalls)++;

  if ( N == 1 ) return 1;
  return F (N - F (N-1, numCalls), numCalls);
}

int main() {
  for (int i = 1; i < 10; i++) {
    int numCalls = 0;
    int result = F(i, &numCalls);
    printf("F(%d) = %d, making %d calls.\n", i, result, numCalls);
  }
}

输出是

F(1) = 1, making 1 calls.
F(2) = 1, making 3 calls.
F(3) = 1, making 7 calls.
F(4) = 1, making 15 calls.
F(5) = 1, making 31 calls.
F(6) = 1, making 63 calls.
F(7) = 1, making 127 calls.
F(8) = 1, making 255 calls.
F(9) = 1, making 511 calls.

请注意,评估F(i)总是需要2次ⁱ -1次调用(就像理论预测的那样!)并且总是返回1,根据经验验证数学分析.