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

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² 但这似乎不是答案。

谁能告诉我为什么？

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ⁿ).

为了验证这一点，这里有一个（非常骇人听闻的）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 次调用（正如理论预测的那样！）并且总是 returns 1 次，根据经验验证数学分析。

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

Give a tight big-oh run-time analysis for this code fragment

algorithm

big-o

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

Give a tight big-oh run-time analysis for this code fragment

algorithm

big-o

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