大きなOの混乱

Question

私はいくつかの機能をテストしていますが、私は時間の複雑さを理解しようとしています。 私の問題はさらにビッグOI上のいくつかの記事にアップ読んだ後、次がどうあるべきかを把握することはできませんということです。

千ループ：15000オブジェクト：時間6

千ループ：30000個のオブジェクト：時刻9

千ループ：60000個のオブジェクト：時間15

千ループ：120000のオブジェクト：時間75

最初の2の差は3 ms、次に6 ms、そして60です。したがって、各繰り返しで時間が倍になります。私はこれがO（n）ではないことを知っています。それはO（log n）ではないと思います。

私は別のデータセットを試してみると、時間が必ずしも上がるとは限りません。たとえば、次のシーケンス（ms）を使用します。11-17-26-90-78-173-300

78ミリ秒が外れています。これも可能ですか？

編集： NVM、私はちょうど私の大学教師とこれを話す必要があります。 時間の出力が異なる変数と多すぎます。 お手数をおかけしていただきありがとうございました！少なくとも3、好ましくは6以上 - あなただけでは理論からO（n）のを取得することはできませんし、私はあなたがO（n）のに大きさのより多くの受注に目を通す必要があると思うと仮定すると

Answer 1

Big O表記は、操作が完了するのに時間がかかりません。これは、一般的な「ステップ」で表現された入力サイズの変更に関して、さまざまなアルゴリズムが漸近的にどのように比較されるかの（非常に粗い）推定です。それは「N個の要素を入力するためにアルゴリズムがどのくらい多くのステップを実行しますか？」です。

Big O表記では、定数は無視されることに注意してください。したがって、各反復で100回の計算を行うN個の要素にわたるループは、100 * NであるがO（N）に等しい。同様に、10000回の計算を行うループは依然としてO（N）になります。あなたの例ではそのため

、あなたのような何かを持っている場合：

for(int i = 0; i < 1000; i++) 
    for(int j = 0; j < N; j++) 
     // computations 

を、それが1000 * N = O（N）になります。

Big Oは、アルゴリズムが実行時間O（N）を持ち、別のものがO（N^2）の場合、最初のものは、最終的にはこの推定には、CPU速度、キャッシング、I/Oボトルネックなど、基本となるプラットフォームに関係するものは考慮されていません。

Answer 2

（nのバリエーションを確認するには、実験する必要があります）。あなたがする必要がある場合は、夜通し稼働しておきます。次に、結果を対数的にプロットします。

基本的に私は今あなたが騒音を見ていると思う。

Answer 3

あなたの実際のアルゴリズムを見なければ、私は推測することができます。 をあなたが3MSの一定の初期化のオーバーヘッドを許可した場合、あなたは

1000x15,000 = (OH:3) + 3 
1000x30,000 = (OH:3) + 6 
1000x60,000 = (OH:3) + 12 

これで終わる、私には、O（n）の

ように見えます

異なるデータセットのタイムスタンプの相違は、いくつかの要因による可能性があります。