0

私はプログラミングの初心者で、最近、漸近的複雑さのトピックを紹介されました。私が興味を持っているのは、要素の数とそれらの並べ替えにかかる時間を考慮して、並べ替え方法の漸近的な複雑さをどのように把握するかということです。

これが私の言いたいことの例です。

  • 「sortArray」が 400 要素のソート済み配列をソートする時間: 4
  • 「sortArray」が 800 要素のソート済み配列をソートする時間: 8
  • 「sortArray」が 1600 要素のソート済み配列をソートする時間: 16

  • 「sortArray」が 3200 要素のソート済み配列をソートする時間: 26

  • 「sortArray」が 400 要素のランダム配列をソートする時間: 255

  • 「sortArray」が 800 要素のランダム配列をソートする時間: 958
  • 「sortArray」が 1600 要素のランダム配列をソートする時間: 4059
  • 「sortArray」が 3200 要素のランダム配列をソートする時間: 16585

このようなものの Big O 表記を計算する方法について何か助けはありますか? ありがとう！

4

1 に答える 1

2

定義上、アルゴリズムの漸近的な複雑さは、入力のサイズが増加するにつれて (時間、空間、またはその他のリソースの) 増加率を表します。この増加率を判断するには、アルゴリズム自体を分析することをお勧めします。ただし、「ブラック ボックス」の並べ替えアルゴリズムしかなく、入力のサイズと結果の時間しかわかっていない場合は、入力対時間のグラフが特定の関数がするパターン。

このアイデアをテストするために、グラフ関数は次のようになります。

  • f(n) = n
  • f(n) = n ln n
  • f(n) = n^2

など、アルゴリズムを実行するために作成した時間のグラフに最も似ているものを確認します。漸近解析では、各項の定数因子と下位項の両方が省略されることに注意してください。したがって、グラフが f(n) = 2n のように見えても、アルゴリズムがまだ線形時間で実行されている場合でも、O(n) アルゴリズムがあります。

于 2010-09-28T18:34:42.783 に答える