0

次の表についてはよくわかりません

代替テキストhttp://files.getdropbox.com/u/175564/algTranslation.png

この表は、アルゴリズムの複雑さが指定されたサイズである場合に、左側の列に指定された制限時間内に解決できる問題のサイズを示しています。

テーブルの控除に興味があります。

表は私にそれを示唆している

  • O（n）= 1秒で10M （これは現在のコンピューターの能力のようです）
  • nは処理するアイテムの数です＃Guffaに感謝します！

O（n * log（n））の列の値がどのように推定されているのかわかりません。

  1. O（n * log（n））の場合は0.5M、O（n ^ 2）の場合は3000の値をどのように推定できますか？
4

3 に答える 3

4

いいえ、nは秒数ではなく、処理するアイテムの数です。

O（n）は、アイテムを処理する時間がアイテムの数に比例することを意味します。

O（n²）は、アイテムを処理する時間がアイテム数の2乗に比例することを意味します。アイテム数を2倍にすると、処理時間は4倍になります。

参照：BigO表記

この表では、アイテムごとに一定量の作業があることを前提としていますが、大きなO表記は、アルゴリズムがアイテム数の変化にどのように反応するかを指定するだけで、アイテムごとの作業量については何も示していません。

編集：
表のx軸に沿った値は、アイテムごとの作業が同じであるという仮定に基づく単なる概算です。たとえば、O（n²）の値3000は、1,000万の平方根から四捨五入されます。これは約3162.28です。1000万の立方根は200ではなく、約215.44です。

実際の状況では、2つのアルゴリズムがアイテムごとに同じ量の作業を行うことはめったにありません。O（log n）を使用するアルゴリズムは、通常、同じ目的でO（n）アルゴリズムよりもアイテムごとにより多くの作業を実行しますが、スケーリングがはるかに優れているため、ほとんどの状況で依然として好ましいです。

于 2009-06-28T11:25:39.520 に答える
1

この表は、一定の時間（1秒、1分、1時間、1日、または1年）を自由に使用できる場合に、さまざまな種類の複雑さに対してnがどれほど大きくなるかを簡単に示していると思います。

例：O（n ^ 3）：

 1 second: 200^3 = 8 000 000 (roughly 10 million, given in O(n) column)
 1 minute: 850^3 = 614 125 000 (roughly 600 million, given in O(n) column))
 1 hour: 3000^3 = 27 000 000 000 (somewhat roughly 35 billion, given in O(n) column)

ご覧のとおり、数値は非常に大まかな概算です。著者は自分の主張を説明するために素敵な丸い数字を使いたいと思っていたようです。

于 2009-06-28T11:50:13.447 に答える
1

1秒あたり10,000,000opsを実行できる場合、n = 500,000に設定し、n * log（n）= 500,000 * log2（500,000）= 500,000 * 18 = 9,000,000 opsを計算すると、「秒」の目的では約10,000,000になります。分類。

同様に、n = 3,000の場合、n ^ 2=9,000,000になります。したがって、すべての行で、操作の数はほぼ同じです。

于 2009-06-28T16:53:54.140 に答える