小さな入力サイズの場合、定数は時間の複雑さに関係しますか？どうやって？

Question

このリンクの時間複雑度&についていくつかの講義を行っていたのですが、https://www.youtube.com/watch?v=__vX2sjlpXU著者は、入力サイズが小さい場合、多くの状況で定数が問題になると説明しています。親切

Answer 1

のが100Nおよび2N の実際の複雑さを持つ2つのアルゴリズムがあるので、彼らはO（n）とO（nは）しているとしましょうを説明します。 n = 2の場合、実行にはそれぞれ200および8CPUサイクルがかかります。しかし、nが50より大きい場合、100nアルゴリズムは常に2n アルゴリズムよりも優れた性能を発揮します。

このように、小さな入力の場合、Big Oはアルゴリズムの優れた判断基準ではなく、定数が入力に比べてかなり大きいときに重要な役割を果たします。 100 + nと、例のような2 + N の時間の複雑さに対処するとき

---

同様に、あなたは結果を理解することができます。定数の影響を追い越すほど大きくないnの値に対して、実際の実行時間は入力値nの代わりに定数によって支配されることになります。

Answer 2

時間複雑度の場合はと関係ありません。

しかし、大きな定数がある場合、プログラムは複雑であっても、複雑なプログラムよりも遅くなる可能性があります。どちらが自明であるかは、1 hourのために眠っていると想像してください。あなたのプログラムは長い間、大きな定数を必要とします。しかし、定数は重要ではないので、その複雑さのクラスは良いかもしれません。

なぜ重要ではありませんか？複雑さのより悪いすべてのプログラムのために、彼らはしばらく遅くなる入力（大きな入力）があるので。ここで

---

は一例です。

グッド複雑O(1)、遅いとにかく：速く

void method() { 
    sleep(60 * 60 * 1_000); // 1 hour 
} 

さらに悪いことに、複雑O(n)、小さな入力用：

void method(int n) { 
    for (int i = 0; i < n; i++) { 
     sleep(1_000); // 1 second 
    } 
} 

ただし入力の場合n > 60 * 60 2番目の方法は遅くなります。

---

あなたは時間を実行し、実際に測定と時間複雑を混同してはならない、それは大きな違いです。

時間の複雑f in O(g)の定義を参照して、およそ漸近境界である：

Answer 3

私は、アルゴリズムとその複雑さについて勉強していましたさて、私たちの教授は簡単に定数aは重要であると説明ロット。複雑性理論には、複雑さを説明するための2つの主な表記法があります。最初はBigO、もう1つは薄い表記です。

ヒープを使用して優先度キューを実装すると、最大要素を削除する場合は2lgN、各項目に挿入する場合は1 + logNとなります。人々は実際には2logNを削除してと書いていますが、それは正しくありません。なぜなら1+logNは要素を挿入するためだけであり、要素を削除するとキュー（シンクと水泳）機能を再調整する必要があるからです。

~2logNをO(logN)と書いた場合、それは1つの機能の複雑さを数えていることを意味します。

参考までに、一部の一流大学では、教授のほとんどが~表記を使用しています。

BigOは危険です。 Robert sedgewick and Kevin Wayneによって書かれた本は~を使用し、なぜ彼がそれを好むかを説明します。