T (1) = c
T (n) = T (n/2) + dn
これのBigOをすばやく決定するにはどうすればよいですか？
4 に答える
2
が何であるかは完全にはわかりませんdnが、定数に を掛けたものを意味すると仮定すると、次のようになりますn。
Wolfram Alpha によると、次の再帰方程式の解:
f(n) = f(n / 2) + cn
は：
f(n) = 2c(n - 1) + c1
これはこれになりO(n)ます。
于 2010-10-31T00:13:02.373 に答える
2
後方置換を繰り返し使用して、パターンを見つけます。ここに例があります。
于 2010-10-31T00:08:32.280 に答える
1
さて、この関係の反復部分は T(n/2) 部分であり、実際には毎回 n の値を半分にしています。
したがって、約が必要になります。(log2 n) ステップで終了条件に到達するため、アルゴリズムの全体的なコストは O(log2 n) です。dn 部分は、各ステップの一定時間の操作であるため、無視できます。
述べたように、n の任意の値を繰り返し半分にすると正確に 1 になる可能性は低いため、問題が必ずしも終了するとは限らないことに注意してください。T(n/2) の部分は実際には T(floor (n / 2))または、これが確実に終了するようにするために、そのようなもの。
于 2010-10-31T00:18:55.597 に答える
0
マスターの定理を使用http://en.wikipedia.org/wiki/Master_theoremを参照
ちなみに、d が正で、n (問題のサイズ) よりも十分に小さいと仮定すると、再帰の漸近挙動は O(n) です。
于 2010-11-01T07:43:04.720 に答える