algorithm - 方法的复杂性

Question

我在采访中被问到这个问题。这种方法的复杂性是什么？

static int magic(int n) {
    System.out.println( count+" "+ n);
    count++;
    return (n < 2) ? n : magic(n - 1) + magic(n - 2);
}

Answer 1

复杂性是指数级的。

除了基本情况（当 n < 2 时），对方法的每次调用都会调用自身两次。您可以绘制表示调用的二叉树。例如，如果您使用 5 作为参数调用魔法：

这棵树不是完全平衡的，但它不会改变大 O 表示法，即 O(2^n)。

您的算法是一种斐波那契序列算法，因此您可以在互联网上阅读大量有关它的信息，包括如何将其复杂性更改为多项式时间。