complexity-theory - 線形の複雑さと二次の複雑さ

Question

よくわかりません...

次のいずれかの複雑さで実行できるコードがある場合：

1. たとえば、次のようなO（n）のシーケンス：2つのO（n）のシーケンス
2. O（n²）

推奨されるバージョンは、線形時間で実行できるバージョンです。O（n）のシーケンスが多すぎて、O（n²）が優先されるような時間はありますか？言い換えれば、ステートメントC x O（n）<O（n²）は定数Cに対して常に真ですか？

なぜまたはなぜそうではないのですか？O（n²）の複雑さを選択する方がよいように、条件に影響を与える要因は何ですか？

Answer 1

ここには2つの問題があると思います。最初に表記法が言うこと、次に実際のプログラムで実際に測定すること

1. 大きなOは、n->無限大の極限として定義されているため、大きなOに関しては、有限定数に関係なく、O（n）<O（n ^ 2）は常に真です。

2. 他の人が実際のプログラムは有限の入力しか処理しないと指摘しているので、c * n> n ^ 2、つまりc> nとなるように、nに十分小さい値を選択することはかなり可能ですが、厳密に言えば、もはや大きなOを扱う

Answer 2

定数Cがnの値よりも大きい場合は、O（n²）アルゴリズムの方が適しています。

Answer 3

O表記には常に暗黙の定数があるため、そうです。nが十分に小さい場合、O（n ^ 2）がO（n）よりも高速になる可能性があります。これは、O（n）の定数がO（n ^ 2）の定数よりもはるかに小さい場合に発生します。

Answer 4

C x O（n）<O（n²）は常に真であるとは限りません。nには条件を逆転させる点があります。

Cが大きく、nが小さい場合、C x O（n）> O（n²）。ただし、Cは常に一定であるため、nが大きな数にスケーリングされる場合、C x O（n）<O（n²）になります。

したがって、nが大きい場合、O（n）は常にO（n²）よりも優れています。