java - 大 o 符号和递归函数

Question

我正在尝试学习 Big-O 表示法，但我在计算递归函数的时间复杂度时遇到困难。

你能帮我理解下面例子的时间复杂度吗？

public int recursiveFunction(int n) {
    if (n == 0) {
        return 0;
    }

    return Math.max(recursiveFunction(rand(n)) + 2,recursiveFunction(n - 1));
}

public int rand(int n) {
    return new Random().nextInt(n - 1);
}

谢谢。

Answer 1

时间将取决于 rand(n) 返回的内容，但如果您采取最坏的情况，这将是 n-2。所以代码简化为:

public int recursiveFunction(int n) {
    if (n == 0) {
        return 0;
    }

    return Math.max(recursiveFunction(n - 2) + 2,recursiveFunction(n - 1));
}

它的渐近上限等于:

public int recursiveFunction(int n) {
    if (n == 0) {
        return 0;
    }

    recursiveFunction(n-1);
    recursiveFunction(n-1);

    return 0;
}

这是一个深度为 n 且分支因子为 2 的递归，因此时间复杂度为 O(2^n)。