0

私は自分のアルゴリズムの効率を理解しようとしていますが、少し混乱しています。私の答えを正当化するための専門家のアイデアが必要なだけです。（多くのリソースがありますが、セットの要素については何も見つかりません）

2 つのループの O(n^2) と言うときは、次のように言うのが正しいです。

n^2 は O(n^3) の要素です

私の理解では、ビッグ O は最悪のケースであり、オメガは最も効率的なケースです。それらをグラフに載せると、n^2 のすべてのケースは O(n^3) の一部なので、最初のケースは正しくありませんか?

n^3 は omega(n^2) の要素です

また、2番目のものについても正しくありません。omega(n^2) の最良のケースのいくつかは、n^3 のすべてのケースにあるわけではないからです!

最後は

theta(2^n) の 2^(n+1) 要素

私はそれを測定する方法がわかりません！

4

2 に答える 2

2

答えを一つずつ挙げていきます。

1.) n^2 は O(n^3)
Trueの要素です
Big-Oh の詳細については、こちらをお読みください。

2.) n^3 は omega(n^2) の要素です
True
オメガ表記を理解するには、こちらをお読みください。

3.) theta(2^n) の 2^(n+1) 要素
True
ここまでで、これが正しい理由がわかるでしょう。(ヒント: 定数係数)

他にご不明な点がございましたらお問い合わせください。

于 2013-08-21T11:33:15.493 に答える