方程式の再帰があるとします: T(n)= T(n-2) + c.. これは、結果として問題のサイズを 2 分の 1 に分割していることを意味し、このアルゴリズムの次数は O(n) です。これは正しいです! ここで、私の式が次のようになるとしT(n)= T(n-2)+cnます.. なぜ次数は n2 (2 のべき乗) になるのでしょうか? 再帰ツリー法やその他の方法でそれが n2 になることを証明したくありません..何が違うのか教えてcくださいcn。
質問する
109 次
1 に答える
1
ここで c と cn の違いを教えてください。
これは、追加作業が常に 1 c(または の場合は 2 T(n -2) + cn) 増加することを意味します。
T(n) = T(n-1) + c
問題のサイズが 1 増加した場合、入力する必要がある追加作業は でありc、これは定数です。
T(n) = T(n-1) + cn
c問題のサイズが 1増えると、最後に問題のサイズを 1 増やしたときよりも、追加する必要がある作業が 1増えます。
つまり、問題のサイズを からnに増やし、追加の作業n + 1が追加されたとします。10c問題のサイズを から に増やすn + 1と、さらに作業n + 2を追加する必要があります。11c
このシリーズで終わります：
d + c + 2c + 3c + 4c + 5c + ...
于 2012-10-07T13:39:51.567 に答える