time - 検査によってプログラムの実行にかかる時間をどのように計算しますか?

Question

先日アルゴリズムの講義に行ったのですが、動的計画法について学んでいました。講師は、フィボナッチを再帰的に解くには指数関数的な時間に近く、線形に解くには 2 次時間がかかると述べました。検査だけでこの種のものをどのように解決しますか？

Answer 1

f_nを決定するために（メモ化なしで）再帰的な実装のみを使用する場合、
f_n-1とf_n-2を計算する必要があります。同様に、
f_n-1はf_n-2とf_n-3に分岐し、f_n-2についても同じです。
したがって、そのような分岐があり、再利用の概念がない場合は、ノードを数えてみてください。
ほとんどの場合、これは指数関数的な実行時間を意味する>2^n になります。
しかし、（あなたが述べたように）線形ファッションを使用すると、線形O(n)になり、二次ではありません!

ただし、マージソートのような分割統治アルゴリズムには注意が必要ですが、
バイナリ除算を使用しますが、ツリーの深さは logn になり、ノードの数は2^logn に等しくなり、 nに等しくなります。