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 の場合) は別として、メソッドへの各呼び出しはそれ自体を 2 回呼び出します。呼び出しを表す二分木を描くことができます。たとえば、5 をパラメーターとしてマジックを呼び出すと、次のようになります。

ツリーは完全にバランスが取れているわけではありませんが、O(2^n) である大きな O 表記は変更されません。

あなたのアルゴリズムはフィボナッチ数列アルゴリズムであるため、複雑さを多項式時間に変更する方法など、インターネットで多くのことを読むことができます。