基本递归函数的运行时复杂度

Question

我正在尝试了解此函数的运行时间之间的对比

public static String f(int N) {
    if (N == 0) return "";
    String s = f(N / 2);
    if (N % 2 == 0) return s + s;
    else            return s + s + "x";
}

和这个函数

public static String f(int N) {
    if (N == 0) return "";
    if (N == 1) return "x";
    return f(N/2) + f(N - N/2);
}

其中字符串连接所花费的时间与字符串的大小成正比。

到目前为止，我认为第一个函数针对输入 N 调用了 log(N) 次，第二个函数调用了 2log(N) 次。那正确吗？除此之外，我不确定如何考虑在每个调用中发生了多少操作。我知道对于第一个函数，在基本情况下有 0 个操作（没有连接），然后是 1 个操作（两个空字符串与长度为 1 的字符串连接？），然后是 2 个操作。一般来说，我相信用 N 调用产生的字符串长度为 N？但我只是不知道从哪里开始考虑这一切是如何加起来的。

对于第二个同样我有点迷茫。我只需要一种方法来进行分析。请记住，我不太擅长使用符号，所以如果您要用符号来炫耀，我将不胜感激您的解释，这将帮助我也遵循这些符号。

Answer 1

对于处理您的分析的方法，我建议简化您的循环。你有 F(n/2) + F(n-n/2)。后半部分可以简化 (F(n-n/2) = F(2n/2 - n/2) = F(n/2))。这意味着您实际上是在每次迭代中调用 f(n/2) 两次，这实际上是 2log(n)。在这两个例子中（我认为）你在重复之外都有严格的恒定时间操作。

据我所知，这两个都应该产生相似的输出，除了在第一个示例中您将为每个奇数 n 添加一个 "x" 。这应该导致额外的 n/2 x 乘以 x 的 log(n) 数？我不完全确定这是否正确。我也相信您的第一个示例在 2log(n) 时间内运行，因为您两次调用 f(n/2) 直到 n 为 0.

注意：我不是最擅长的，但我尽力了。

基本递归函数的运行时复杂度

Runtime Complexity of Basic Recursive Functions

recurrence