フィボナッチ アルゴリズムがあるとします。
このアルゴリズムの上限/下限を証明するよう求められます。
続行するにはどうすればよいですか？
アップデート
そこで、私が自分で行ったことを説明し、行き詰まっている場所を示します。
理由はわかりませんが、ここで再帰関係を使用して、最終結果が得られる場所を確認することにしました。しかし、私が自分のワークアウトを疑う理由は、上限/下限が、リソースの観点からのアルゴリズムの「無限」の識別であるためです。
したがって、並列アルゴリズムには次のものがあります。
仕事(n) = W(n - 1) + W(n - 2) + Θ(1)
この時点で、再帰関係を使用することにしました-わかりません-
Work(n) = [W(n - 1) + W(n - 2) + Θ(1)] + W(n - 2) + Θ(1)
= W(n - 2) + W(n - 2) + 2Θ(1)
= 2W(n - 2) + 2
= Stuck here
正直、意味があるかどうかもわかりません。
正式な解決策が与えられました：
しかし、私は上記の手順をよく理解していませんでした