「アルゴリズムAのワーストケース実行時間」と「アルゴリズムAの実行時間はO(n)」の間に違いがありますか?
最悪の場合は関数が取ることができるピーク実行時間であるため、O(n)は関数が「境界」であることを意味するため、「違いはありません」と私は思う。どちらも同じ意味です。
私の論理が正しいことを願っています。
回答:
回答№1の場合は7違いがあります。
アルゴリズムはO(f)は正確ではありません:あなたはalgirthmが最高/最悪/平均の場合にはO(f)であると言わなければなりません。最高、最悪、および平均が同じだが、それほど一般的ではない場合、それはO(f)と言うことができます。
回答№2の場合は1
私はあなたの感情に同意しますが、共通点があります予想される時間が最悪の場合よりもはるかに良いアルゴリズム(例えば、クイックソート)。クイックソートはO(N ^ 2)最悪のケースだと主張することができますが、あなたはまだそれがO(N * log N)であると予想しています。
また、アルゴリズムが複雑になる償却された行動をしている。 1つの特定の操作に対してO(N)またはO(log N)を得ることができますが、行内の多くの操作は、償却された意味では常にO(1)になります。このカテゴリでは、スプレイツリーとフィンガーツリーが良い例です。
回答№3の場合は1
絶対的な手段としての演奏時間は、通常、 データを追加するとその時間がどのように増加するか。例えば、常に5をとるアルゴリズム100項目を処理する秒数、200項目を処理する10秒間などは、実行時間がデータセットのサイズに比例して増加するため、O(N)と言います。 2番目のアルゴリズムがこれらの200個のアイテムを処理するのに5 * 5 = 25秒かかる場合、O(N ^ 2)として分類される可能性があります。より多くのデータを投げると、実行時間は常に増加するため、ここでは「ピーク実行時間」はありません。
実際、大きなOは上限です。最初のアルゴリズムもO(N ^ 2)であったとします(Nが上限であればN * Nが高く、したがって上限も低くなります)。他の境界を示す一般的な表記には、Ω(オメガ、下限)とΘ(シータ、下限と上限の同時)が含まれます。
いくつかのアルゴリズム(Quicksortなど)は、それに供給されるデータに応じて異なる動作を示します。したがって、通常はO(N log N)のように動作しますが、最悪のケースはO(N ^ 2)です。
回答№4の場合は0
これらの文字列には大きな違いがあります言葉の「アルゴリズムAの最悪実行時間」は名詞句であり、全く文を作成しません。 "アルゴリズムAの実行時間はO(n)です"は文であり、Aについて何かを教えてくれます。