algorithm - 同じ関数のいくつかの大きな O 表記

Question

させてf(n)= ( (n^2+2n)/n + 1/1000*(n^(3/2)))*log(n)

この関数の時間計算量は、両方の可能性がありますO(n²*log(n)) and O(n^(3/2)*log(n))

これはどのように可能ですか？ここで支配的な用語は であると思ったので、ビッグOn² (*log(n))表記のみにする必要があり、時間の複雑さの尺度は非常に曖昧に感じますO(n²*log(n))

Answer 1

Big O表記はそれほど混乱しません。これはアルゴリズムの実行時間の上限を定義します。したがって、がO(f(n))有効な上限である場合、コードが 未満で実行される場合、確実に 未満で実行されるため、 が確実に有効である場合はすべて が有効です。O(g(n))g(n) > f(n)f(n)g(n)

あなたの場合、O(n^2 *log(n))dominatesO(n^(3/2) log(n))であるため、それほど厳密ではなくても有効な上限です。さらに、あなたのアルゴリズムはO(n^3). 問題は、これらの Big O 表記のどれが、アルゴリズムに関するより多くの情報を提供してくれるかということです。明らかな答えは低い方であり、それが通常それを示す理由です。

わかりやすくするために、ボールを 10 メートル上に投げることができるとしましょう。その場合、10m より高くは投げられない、または 15m より高くは投げられないと言うことができます。最初のものがより厳密な上限であるという事実は、2 番目のものを虚偽のステートメントにするものではありません。

Answer 2

合計に適用される"ビッグ O 表記法" は、常に支配的な (最大の) 項のみを残します。独立変数が 1 つの場合、1 つの項だけが生き残ります。あなたの場合

  O(n^2*log(n) + n^(3/2)*log(n)) = O(n^2*log(n))

第 1 項は第 2 項よりも大きいため、次のようになります。

  lim(term1/term2) = lim(n^2*log(n) / (n^(3/2)*log(n))) = lim(n^(1/2)) = inf

しかし、計算で算術エラーを起こしたようです:

  (n^2+2n)/n = n + 2, not n^2 + 2 * n

その場合

  O(n*log(n) + 2*log(n) + n^(3/2)*log(n))

「n^(3/2)*log(n)」である最後の項は最大のものです

  O(n*log(n) + 2*log(n) + n^(3/2)*log(n)) = O(n^(3/2)*log(n))