java - 入门方法 Big-O 复杂性

Question

当你在考虑一个调用递归方法(引子方法)的方法的复杂度时，你是考虑递归方法的复杂度，还是只考虑方法的调用。

例如，我有一个计算斐波那契数列的小程序:

// 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 并返回一个数字。

Answer 1

My assumption is that it is complexity 1 because all it does is define and int and return a number.

作为事实陈述，您的“所有内容都是......”这不是真的。 f(9) 的值也正在计算中。 (它可以在“编译时”计算，但它仍然在计算。)由于你的论点的前提并不严格正确......无法得出结论。

忽略这个狡辩，你的解释直观上是正确的，但从严格的数学角度来看却站不住脚。

更好的解释是选择一些数学变量(例如Q)。然后我们可以说，相对于该变量，fib() 的时间复杂度为 O(1) 。

(请注意，n 在此上下文中不是变量，除了 pi 或 e 都是变量。)

或者您可能会说 fib() 的复杂性分析毫无意义，除非您确定了感兴趣的输入变量。

从数学角度(IMO)来看，这两种看待这个问题的方法更有意义。O 公认的数学定义假设存在一个变量。 O 复杂度描述了函数相对于该变量的行为。