値を並べ替える私のプログラムは、次の時刻に実行されます。
- 100000 8秒
- 1000000 82s
- 10000000 811s
それはO(n)ですか？
8 に答える
17
見た目はそうですが、実際には、データに基づいてさまざまなケースが存在する可能性があるため、アルゴリズムを分析する必要があります。たとえば、一部のアルゴリズムは、事前に並べ替えられたデータで良くも悪くもなります。あなたのアルゴリズムは何ですか？
于 2009-11-13T15:33:58.277 に答える
10
はい、それは私には O(n) のように見えます - 1 番目から 2 番目のケースと 2 番目から 3 番目のケースに行くと、入力が 10 倍大きくなり、10 倍長くかかります。
特に、以下を使用して大まかな時間を予測できるようです。
f(n) = n / 12500
また
f(n) = n * 0.00008
これは、提供されたデータの O(n) の最も簡単な説明を提供します。
編集：ただし...指摘されているように、データが誤解を招く可能性があるさまざまな方法があります.IOコストが他のすべてのものを圧倒しているというDennis Palmerの考えが好きです。たとえば、操作の絶対数が次のアルゴリズムがあるとします。
f(n) = 1000000000000n + (n^2)
その場合、複雑さは依然として O(n^2) ですが、n が非常に大きくなるまで観測から明らかになりません。
これらの観察結果は O(n) アルゴリズムを示唆していると言うのは正確だと思いますが、それが確実にそうであるとは限りません。
于 2009-11-13T15:32:36.413 に答える
8
時間の振る舞いはそのようには機能しません。本当に言えることは、これら 3 つのデータセットが互いにほぼ O(n) 離れているということだけです。それは、アルゴリズムが O(n) であることを意味しません。
最初の問題は、指数関数 ( O(e**n) ) になる曲線を簡単に描くことができ、それでもこれら 3 つの点が含まれていることです。
ただし、大きな問題は、データについて何も言わなかったことです。並べ替えられた、またはほぼ並べ替えられた入力に対して O(n) に近づく多くの並べ替えアルゴリズムがあります (例: Mergesort)。ただし、それらの平均的なケース (通常はランダムに並べられたデータ) と最悪のケース (多くの場合、逆に並べ替えられたデータ) は、常に O(nlogn) またはそれよりも悪いものです。
于 2009-11-13T15:48:20.700 に答える
4
わかりません。
まず、時間はデータ、環境、およびアルゴリズムによって異なります。ゼロの配列があり、それをソートしようとすると、プログラムの実行時間は 1000 個の要素でも 1000000 個の要素でもそれほど変わらないはずです。
次に、O 表記は、n0 から始まる n の大きな値に対する関数の動作を示します。g(n) 関数のように、アルゴリズムが特定の入力サイズまで適切にスケーリングされ、その動作が変化する可能性があります。
于 2009-11-13T16:31:52.763 に答える
2
はい、それはアイテムの数に比例するため、O（n）です。
1000000 = 10 * 100000
と
82s = 10 * 8s (roughly)
于 2009-11-13T15:34:04.960 に答える
2
私にはO(n)のように見えます。
于 2009-11-13T15:32:21.480 に答える
2
それが O(n) であるとは言えません。たとえば、バブルソートは n ステップで完了できますが、O(n^2) アルゴリズムです。
于 2009-11-13T16:06:36.263 に答える
1
はい、O(n) のように見えますが、アルゴリズムのタイミング パフォーマンスに基づいて決定的に分析できるとは思いません。最も非効率的な並べ替えアルゴリズムを使用している可能性がありますが、データの読み取り/書き込み時間が合計実行時間の大部分であるため、O(n) 時間の結果が得られます。
編集: Big-O は、アルゴリズムの効率性とスケーリング方法によって決まります。入力項目数の増加に伴う実行時間の増加を予測する必要があります。逆は必ずしも真ではありません。実行時間の特定の増加を観察することは、いくつかの異なることを意味する可能性があります。あなたが与えた例の数字に忠実であれば、あなたのプログラムは O(n) で実行されると結論付けることができますが、他の人が言ったように、それはあなたのソートアルゴリズムが O(n) であることを意味しません.
于 2009-11-13T15:48:49.823 に答える