次の方程式の大きな複雑さは O(n^3) であることを知っています
4n^3 + 6n + 6
n^3 が支配的な項だからです。
大きな複雑さは同じ関数で同じですが、負の係数がありますか?
-4n^3 + 6n + 6
5294 次
2 に答える
2
正式には、単調に増加する関数を分析します。これは、漸近的な複雑さの正式な定義によって暗示されています。
ウィキペディアで定義の1つを見てみましょう：
1つの書き込み
f（x）= O（g（x））as x-> inf
xのすべての十分に大きな値に対して、f（x）が最大でMに絶対値でg（x）を掛けたような正の定数Mがある場合に限ります。つまり、正の実数Mと実数x0が存在する場合に限り、f（x）= O（g（x））となります。
| f（x）| <= M | g（x）| すべてのx>x0に対して
ご覧のとおり、この定義は絶対値で機能します。
他のいくつかの情報源（データ構造やアルゴリズムに関する本など）では、絶対値のない定義が見つかる場合がありますが、分析された関数の仮定が単調に増加している場合があります（警告：仮定が本の参照に隠されているか、分析されたユニバースのプロパティによって暗示されている場合があります）。
要約すると、漸近解析は単調に増加する関数で使用するように設計されています。仮定によって強制される場合もあれば、方程式の絶対値によって強制される場合もあります。
あなたはこの別のSOの答えのような他のagrugmentsを見つけるかもしれませんが、同じ結論です。
于 2012-10-24T15:20:29.667 に答える
2
実際、big-O 計算に負の項がある場合は、それらが時間の獲得につながるため、それらを無視できます。
この場合、複雑さは になりますO(n)。
ただし、そのようなものがどのようなアルゴリズムに対応できるかはわかりませんが、一般的な質問に答えるために、複雑さを与えるようなものを持つことができます。O(an^2 - bn)O(n^2)
編集：
アルゴリズムの解決における時間旅行について、面白い関連の質問を見つけました。
于 2012-10-23T21:28:39.253 に答える