java - 大符号和递归函数

我正在尝试学习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);
}

谢谢。

最佳答案

时间取决于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)时间复杂度。