引物方法 Big-O 复杂性
Primer Method Big-O Complexity
当你在考虑调用递归方法(引子方法)的方法的复杂度时,你是考虑递归方法的复杂度,还是只考虑方法的调用。
比如我有一个计算斐波那契数列的小程序:
// Complexity: ???
public int fib() {
int n = 9;
return fib(n);
}
// Complexity: O(2^n)
private int fib(int n) {
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
递归fib(int n)
方法的复杂度是O(2^n)
,但我不确定fib()
的复杂度是多少。
我的假设是它的复杂度为 1,因为它所做的只是定义和 int 以及 return 一个数字。
My assumption is that it is complexity 1 because all it does is define and int and return a number.
作为事实陈述,您的"all its does ..."是不正确的。 f(9)
的值也在计算。 (它可以在 "compile time" 处计算,但它仍然在计算。)由于你的论点的前提并不严格正确......无法得出结论。
忽略那个狡辩,你的解释在直觉上是正确的,但从严格的数学角度来看是站不住脚的。
更好的解释是选择一些数学变量(比如Q
)。然后我们可以说 fib()
的时间复杂度是 O(1)
相对于那个变量 。
(请注意,n
在此上下文中不是变量,而 pi
或 e
是变量。)
或者您可以说 fib()
的复杂性分析没有意义,除非您确定了感兴趣的输入变量。
这两种看待这个问题的方式从数学角度 (IMO) 更有意义,O
公认的数学定义假设存在一个变量。 O
复杂性表征函数关于该变量的行为。
当你在考虑调用递归方法(引子方法)的方法的复杂度时,你是考虑递归方法的复杂度,还是只考虑方法的调用。
比如我有一个计算斐波那契数列的小程序:
// Complexity: ???
public int fib() {
int n = 9;
return fib(n);
}
// Complexity: O(2^n)
private int fib(int n) {
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
递归fib(int n)
方法的复杂度是O(2^n)
,但我不确定fib()
的复杂度是多少。
我的假设是它的复杂度为 1,因为它所做的只是定义和 int 以及 return 一个数字。
My assumption is that it is complexity 1 because all it does is define and int and return a number.
作为事实陈述,您的"all its does ..."是不正确的。 f(9)
的值也在计算。 (它可以在 "compile time" 处计算,但它仍然在计算。)由于你的论点的前提并不严格正确......无法得出结论。
忽略那个狡辩,你的解释在直觉上是正确的,但从严格的数学角度来看是站不住脚的。
更好的解释是选择一些数学变量(比如Q
)。然后我们可以说 fib()
的时间复杂度是 O(1)
相对于那个变量 。
(请注意,n
在此上下文中不是变量,而 pi
或 e
是变量。)
或者您可以说 fib()
的复杂性分析没有意义,除非您确定了感兴趣的输入变量。
这两种看待这个问题的方式从数学角度 (IMO) 更有意义,O
公认的数学定义假设存在一个变量。 O
复杂性表征函数关于该变量的行为。