私は最近、再帰と Big-O 記法を含むコンピューター サイエンスの宿題に取り組んでいます。私はこれをかなりよく理解していると思います (ただし、完全ではないことは確かです!)。奇妙なことに、それを見ると、宿題の中で最も単純なもののように見えます。
次の再発の解決策として、big-Oh 表記法を使用して最高の成長率を提供してください。
T(1) = 2
T(n) = 2T(n - 1) + 1 for n>1
選択肢は次のとおりです。
- O(n log n)
- O(n^2)
- O(2^n)
- O(n^n)
大きな O が上限として機能し、プログラムまたはプロセスにかかる最大の計算量または最大実行時間を表すことを理解しています。この特定の再帰は O(n) であるべきだと思います。なぜなら、再帰は n の値ごとに 1 回しか発生しないからです。n が利用できないので、他の 3 つのオプションである O(nlogn) よりも良いか、悪いかのどちらかです。
だから、私の質問は: なぜこれは O(n) ではないのですか?