大写符号和递归函数

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)时间复杂度.