アルゴリズムの複雑さと実行時間

Question

私は信号量子化に使用されるアルゴリズムを持っています。アルゴリズムのために、私はパラメータの異なる値でその複雑さを計算する方程式を持っています。このアルゴリズムはC言語で実装されています。時には方程式に従うと複雑さは少なくなりますが、実行時間は長くなります。私は方程式について100％確信していません。

私の質問は、実行時間とアルゴリズムの複雑さは、まっすぐな関係を持っていますか？私たちが持つ複雑性が高いほど、実行時間は長くなります。それとも、あるアルゴリズムと別のアルゴリズムですか？

Answer 1

時間の複雑さは、入力サイズによって時間がどのように変化するかを、絶対的な尺度よりも測定します。
（これは極端な単純化であるが、それはあなたが見ている現象を説明するために行います。）

nがあなたの問題の大きさであり、あなたの実際の走行時間が1000000000 * nある場合0.000000001*n^2は次のようになりながら、それは、線形複雑度を持っています二次関数

お互いにプロットすると、0.000000001*n^2は、 "より複雑である"にもかかわらず、n = 1e18付近まで、1000000000 * nよりも小さくなります。

（0.000000001*n^2 + 1000000000 * nも二次であってもよいが、必ず両方よりも悪いの実行時間を持つことになります。）

Answer 2

いいえ、時間とアルゴリズムの複雑さを実行すると、単純な関係を持っていません。

実行時間の見積もりや比較は、簡単に非常に複雑で詳細になることがあります。同じプログラムや入力データであっても変わる変数はたくさんあります。そのため、ベンチマークは複数の実行を行い、それらを統計的に処理します。

大きな違いがある場合は、アルゴリズムの複雑さ（「大きなO（）」）と起動時間の2つの最も重要な要素があります。頻繁に、より小さい「大きい（）」アルゴリズムは、より複雑な起動を必要とする。つまり、実際のループに入る前に、プログラムでより多くの初期設定が必要になります。小さなデータセットの残りのアルゴリズムを実行するより時間がかかる場合は、（）定格アルゴリズムは、小さなデータセットの方が速く実行されます（）。大きなデータセットの場合、（）アルゴリズムの方が高速になります。合計時間が等しい、「クロスオーバー」サイズと呼ばれるデータセットサイズがあります。

パフォーマンスを向上させるには、実装するアルゴリズムの選択の一環として、データの大部分がクロスオーバーの上または下にあるかどうかを確認することをお勧めします。

ランタイム予測の詳細と精度がますます複雑になってきています。