引物方法 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 在此上下文中不是变量,而 pie 是变量。)

或者您可以说 fib() 的复杂性分析没有意义,除非您确定了感兴趣的输入变量。

这两种看待这个问题的方式从数学角度 (IMO) 更有意义,O 公认的数学定义假设存在一个变量。 O 复杂性表征函数关于该变量的行为。