アルゴリズム複雑度に関する簡単なタスクの解法

だからここで解決策です.読みやすい質問を繰り返す
非常に悪いフィボナッチの実装を紹介します.

function fib(n) {
    if (n <= 1) {
        return 1
    }
    return fib(n - 2) + fib(n - 1)
}

最初の質問はとても簡単です.

Q1. What's wrong with this implementation and how to fix it?

アンサー

実装は、不要な作業の多くを作る1つの数を複数回再計算します.より効率的な実装は単純なfor -ループです.

function betterFib(n) {
    let r1 = 1;
    let r2 = 1;
    for (let i = 2; i <= n; i++) {
        const _r2 = r2;
        r2 = += r1;
        r1 = _r2;
    }
    return r2;
}

それは“機能的に純粋ではない”、それはうまく翻訳された数学の式のように見えません.しかし、それは速い作品!

Q2. What's it complexity in terms of ? How to estimate and prove it?

アンサー

それは指数関数です.しかし、それは正確には見えません
O ( 2 n ) O ( 2 ^ n ) O ( 2 n )
すべての呼び出しが2つの再帰的な呼び出しを生じるというわけではないので、それは「左」再帰呼び出しfib(n - 2)が「正しい」ものより速く再発ベースに達するので、それです.呼び出し木をスケッチしましょう.

Sketchpad
それは、指数的に非等しい側で若干の空想的な図に見えます😄 そして、タスクはその「面積」を計算することに等しいです.私はそれを正確に計算するための簡単な方法だが、それは確かにその限界を推定することだ!

辺が等しい、そして、図形高さが元の図の左側のそれと等しいならば、結果として生じる面積は
O ( 2 n/2 ) O ( 2 ^{ n/2 }) O ( 2 n/2 )

辺が等しい、そして、高さが元の図の右側のそれと等しいならば、結果として生じる面積は
O ( 2 n ) O ( 2 ^ n ) O ( 2 n )

そして、それは答えです!複雑さ
XXX
本来の機能fibの間隔は、
O ( 2 n/2 )< x < o ( 2 n ) O ( 2 ^{ n/2 })< x < o ( 2 ^ n ) O ( 2 n/2 )< x < o ( 2 n )
このソリューションを読んでくれてありがとう.あなたが問題声明でポストを読んだならば、二重に感謝します.トリプルのおかげで試してみてください!あなたが面白いもののこの種を見つける場合はいくつかのフィードバックを残して検討してくださいので、私は短く、楽しいプログラミング演習を発表し続けます.感謝🙏