我正在尝试学习 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)。
关于java - 大 o 符号和递归函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14123008/