recursion - 以下递归代码的时间复杂度（大 O 表示法）？

Question

以下递归代码的 Big-O时间复杂度（ ）是多少？O

public static int abc(int n) {
    if (n <= 2) {
        return n;
    }
    int sum = 0;
    for (int j = 1; j < n; j *= 2) {
        sum += j;
    }
    for (int k = n; k > 1; k /= 2) {
        sum += k;
    }
    return abc(n - 1) + sum;
}

我的回答是O(n log(n))。这是对的吗？

Answer 1

我坐在哪里......我认为运行时间是O(n log n)。这就是为什么。

• 您正在对该函数进行n次调用。该函数肯定依赖于n进行以下两个操作的次数：

  • 您最多循环 2*log(n) 值以增加总和。

在最坏的情况下，n非常大，但整体运行时间不会改变。最好的情况是n <= 2，这样只完成一个操作（不会发生循环）。