time-complexity - 最悪のケース vs O(n)

Question

「アルゴリズムAの最悪の場合の実行時間」と「アルゴリズムAの実行時間はO(n)」というステートメントに違いはありますか?

私が「違いはない」と思うのは、最悪の場合は関数がかかるピーク実行時間であり、O(n) は関数が「制限されている」ことを意味するためです。どちらも同じ意味です。

私の論理が正しいことを願っています。

Answer 1

違いがあります。

アルゴリズムは O(f) です 正確ではありません: アルゴリズムは、最良/最悪/平均の場合に O(f) であると言わなければなりません。最良、最悪、平均が同じ場合、それは O(f) であると言えますが、それはあまり一般的ではありません。

Answer 2

通常、絶対的な尺度としての実行時間は、データを追加したときに時間がどのように増加するかよりも重要ではありません。たとえば、100 個のアイテムを処理するのに常に 5 秒、200 個のアイテムを処理するのに 10 秒かかるアルゴリズムは、実行時間がデータセットのサイズに比例して増加するため、O(N) と呼ばれます。2 番目のアルゴリズムが 200 個のアイテムを処理するのに 5*5 = 25 秒かかった場合、O(N^2) として分類される可能性があります。より多くのデータを投入すると実行時間は常に増加するため、ここには「ピーク実行時間」はありません。

実際、大きな O は上限です。したがって、最初のアルゴリズムも O(N^2) であると言えます (N が上限である場合、N*N はより高く、したがって、より緩いものではありますが、上限でもあります) ）。他の境界を表す一般的な表記には、Ω (オメガ、下限) と Θ (シータ、下限と上限の同時) が含まれます。

一部のアルゴリズム (たとえば、クイックソート) は、供給されるデータに応じて異なる動作を示します。したがって、通常は O(N log N) のように動作しますが、最悪のケースは O(N^2) になります。

Answer 3

私はあなたの意見に同意しますが、一般的なアルゴリズム (たとえばクイックソート) では、最悪の場合の時間よりもはるかに優れた時間が予想されます。クイックソートは最悪の場合 O(N^2) であると主張できますが、ほとんどの場合 (少なくとも適切な実装では) O(N*log N) であると予想されます。

また、償却された動作を持つアルゴリズムでは複雑になります。1 つの特定の操作に対して O(N) または O(log N) を取得する場合がありますが、連続する多くの操作は、償却された意味で常に O(1) になります。スプレー ツリーとフィンガー ツリーは、このカテゴリの良い例です。

Answer 4

これらの一連の単語の間には大きな違いがあります。「アルゴリズム A の最悪の場合の実行時間」は名詞句であり、まったくステートメントになりません。「アルゴリズム A の実行時間は O(n) です」は、A について何かを伝える文です。