大きなO表記について学んでいて、ちょっと混乱しています。「複雑さ」がアルゴリズムにどのように影響するかを本当に理解しているとは思いません。また、物事を逆に見ているかどうかもわかりません。
O(1)、O(log n)、O(n)、O(n log n)、O(n^2)? または私はそれを後方に持っていますか？
これが正しい順序である場合、O(n^2) の複雑さを持つプログラムは、O(n log n) のプログラムよりも高速に大量のデータ セットを処理すると推測できます。ただし、バブル ソート (O(n^2)) とクイック ソート (O(n log n)) をテストすると、O(n^2) ソートは O(n log n) よりも処理速度が遅いことがわかります。だから私は混乱しています....複雑さは良いですか悪いですか？アルゴリズムがより複雑であれば、(プログラムを完了するのにかかる時間に関して) 高速になりますか、それとも複雑なプログラムは遅くなりますか?
O表記は、アルゴリズムが処理するオブジェクトを持つ要素の最大数でコンピューターが実行する操作の数を意味します。たとえば、O(n^2) のアルゴリズムを使用して 3 つの要素を持つ配列を並べ替えると、コンピューターは配列に対して最大9 回の操作を実行することになります。
ここでは、さまざまな O の複雑さの比較を見ることができます。
最初の質問に答えるには、はい、これは複雑さの正しい順序です。Big O 表記は、プログラムまたはアルゴリズムの実行にかかる時間を示しません。単純に、複雑性が高いまたは複雑性が低い別のアプローチに関して、そのパフォーマンスを測定します。概念化を助けるために、O(1)は単一の命令、O(n)は単一のループ、O(n^2)は内部にネストされたループを持つループになります。
O(n^2)がO(n log n)よりも速いという質問に答えるには、おそらくそうではないでしょう。おそらく、プログラムの速度を決定する多くの要因があり、複雑さが悪いプログラムの方が複雑さが良いプログラムよりも速く実行される可能性があるためです。言い換えれば、Big O 記法はアルゴリズムの複雑さを測定するものであり、そのアルゴリズムを構成するプログラムを測定するものではありません。
たとえば、簡単にするために、1 つはO(n)時間で実行され、もう 1 つはO(n^2)時間で実行される 2 つのプログラムがあるとします。
10 個のオブジェクトに対して実行すると、 O(n)時間のプログラムは 100 ミリ秒になります。O(n^2)時間でプログラムを実行すると、10 ミリ秒になります。何故ですか？最初のプログラムよりもO(n^2)時間少ない時間でプログラムがジョブを実行するためです 。
しかし、100 個のオブジェクトで何が起こるか見てみましょう。O(n)時間のプログラムは 1000 ミリ秒になり、 O(n^2)時間のプログラムも 1000 ミリ秒になります。より大きなオブジェクトの場合ははるかに速く成長するため、一般的に言えば、複雑さを最適化することをお勧めします。
一部のアルゴリズムでは、複雑さを軽減することはできません。巡回セールスマン問題の一種で、訪問する必要があるすべての都市を通過する特定の長さのパスが存在するかどうかを尋ねます。最良のソリューションを保証するには、考えられるすべてのシナリオを実行する必要があります。これには、O(n!)という Big O 表記があり、最悪です。幸いなことに、はるかに高速に実行できる 98% 以内の解を決定できる代替アルゴリズムが多数あります。O(n!)時間で実行される一連の既知の問題はNP 問題と呼ばれます。
それがあなたの質問に答えることを願っています。