必要なすべての情報が得られない場合、コンピュータ サイエンスにおける Big-O 表記の使用は何ですか?
たとえば、1 つのアルゴリズムが で実行され1000n、もう1 つのアルゴリズムが で実行される場合n、両方とも であることが真ですO(n)。しかし、この情報に基づいて愚かな選択をする可能性もあります。与えられた入力に対して、一方のアルゴリズムは他方のアルゴリズムの 1000 倍の時間がかかるからです。
情報に基づいた選択を行うには、定数を含む方程式のすべての部分を知る必要がありますが、この「中間」比較の重要性は何ですか? 重要な情報がこの形に縮小されると失われてしまいますが、何を得ることができますか?
その定数係数は何を表していますか? たとえば、O(1000n) のアルゴリズムが O(5n) のアルゴリズムよりも遅くなるとは断言できません。1000n アルゴリズムはすべてのデータをメモリにロードし、そのデータに対して 1,000 回のパスを作成し、5n アルゴリズムは低速の I/O デバイスに保存されているファイルに対して 5 回のパスを作成する可能性があります。1000n アルゴリズムは、その「定数」がはるかに大きくても、より高速に実行されます。
さらに、一部のコンピューターは、他のコンピューターよりも高速に一部の操作を実行します。2 つの O(n) アルゴリズム (A と B と呼びます) を考えると、A が一方のコンピューターでより高速に実行され、B が他方のコンピューターでより高速に実行されることは非常に一般的です。または、同じアルゴリズムの 2 つの異なる実装が、同じコンピューター上で大きく異なるランタイムを持つ可能性があります。
他の人が言ったように、漸近分析は、アルゴリズムの実行時間が入力のサイズによってどのように変化するかを示します。これは、アルゴリズムの選択において適切な出発点を提供するのに役立ちます。クイック リファレンスでは、特定のアルゴリズムが O(n) や O(n log n) などであることがわかりますが、最も一般的なアルゴリズムに関する詳細情報を簡単に見つけることができます。それでも、そのより詳細な分析は、その数値が実際の実行時間にどのように関連しているかを知らずに、一定の数値しか得られません.
最終的に、どのアルゴリズムが自分に適しているかを判断する唯一の方法は、それを自分で研究し、予想されるデータに対してテストすることです。
要するに、漸近分析に期待しすぎていると思います。これは便利な「最初の行」フィルターです。しかし、それを超えると、より多くの情報を探す必要があります。
あなたが正しく指摘したように、アルゴリズムの正確な実行時間に関する情報は得られません。主に、アルゴリズムの複雑さを示すために使用され、入力サイズが線形か、2 次か、指数関数かなどを示します。これは、入力サイズが大きいことがわかっている場合にアルゴリズムを選択するときに重要です1000n。1.23 exp(n)十分な大きさのアルゴリズムを打ち負かしnます。
現実世界のアルゴリズムでは、隠れた「スケーリング係数」はもちろん重要です。したがって、スケーリング係数が低い場合、複雑さが「悪い」アルゴリズムを使用することは珍しくありません。ソートアルゴリズムの多くの実用的な実装は、たとえば「ハイブリッド」であり、 の場合は挿入ソート(O(n^2)実装は非常に簡単ですが)のような「悪い」アルゴリズムに頼り、 の場合はクイックソート(ただしより複雑です) にn < 10変更されます。O(n log(n))n >= 10
定数項の隠れた影響に加えて、複雑さの表記は、問題の最悪のケースのインスタンスのみを考慮します。
適切な例として、シンプレックス法 (線形計画法) は、既知のすべての実装で指数関数的な複雑さを持ちます。ただし、シンプレックス法は、証明可能な多項式時間の内点法よりも実際にははるかに高速に機能します。
複雑さの表記法は、理論的な問題の分類に大きな価値があります。実際の結果についてさらに詳しい情報が必要な場合は、Spielman による「Smoothed Analysis」を参照してください: http://www.cs.yale.edu/homes/spielman
これはあなたが探しているものです。
その主な目的は、ロジックの大まかな比較です。と の差は( n はほぼ 1000 に等しい) とO(n)で大きくなりますが、 (n が 1000 よりはるかに大きい)値と比較すると、その差はごくわずかです。O(1000n)n ~ 1000n < 1000n >> 1000
どちらも線形にスケーリングし、係数を知ることは詳細な分析に役立ちますが、一般に、線形 ( O(cn)) と指数 ( O(cn^x)) のパフォーマンスの違いを計算する際には、2 つの線形時間の違いよりも注意することが重要です。パフォーマンスの差が指数関数的に拡大する や などの高次の実行時間の比較では、より大きな値があります。
Big O 表記の全体的な目的は、アルゴリズムを比較してさらに最適化するために、相対的なパフォーマンス時間の感覚を与えることです。
Big-O は、入力のサイズが変化するにつれて、プロセスのランタイムまたはメモリ消費量がどのように変化するかを示します。O(n) と O(1000n) はどちらも O(n) のままです。入力のサイズを 2 倍にすると、すべての実用的な目的で実行時間も 2 倍になります。
ここで、nの係数が 1000000 で n 2の係数が 1 である O(n) アルゴリズムと O(n 2 ) アルゴリズムを使用できます。この場合、O(n 2 ) アルゴリズムは O( n) n 値が小さい場合。ただし、これは、2 番目のアルゴリズムのランタイムが最初のアルゴリズムよりも急速に成長するという事実に変わりはありません。これは、big-O が教えてくれる情報です。O(n) アルゴリズムが O(n 2 ) アルゴリズムよりも優れた性能を発揮し始める入力サイズがいくつかあります。
すべての情報が得られるわけではないことは確かですが、それを行う単一の指標はどの分野にもありません。
Big-O 表記は、データセットが大きくなるにつれてパフォーマンスが低下する速さを示します。つまり、パフォーマンスカーブのタイプを記述しますが、絶対的なパフォーマンスは記述しません。
一般に、Big-O 表記は、アルゴリズムのスケーリング パフォーマンスを表すのに役立ちます。これは、次の 3 つの基本カテゴリのいずれかに分類されます。
非常に正確なパフォーマンス測定のためにアルゴリズムの詳細な分析を行うことは可能ですが、パフォーマンスの大まかな指標を得るには時間がかかり、実際には必要ありません。