大きなO表記とその親戚、大きなシータ、大きなオメガ、小さなo、小さなオメガは、関数が限界点でどのように動作するかについて何かを言う方法です（たとえば、無限大に近づくときだけでなく、近づくときも） 0など）機能については何も言わずに。これらは、アルゴリズムの実行スペースと時間を説明するために一般的に使用されますが、漸近的動作に関する数学の他の領域でも見られます。
半直感的な定義は次のとおりです。
関数g（x）は、「ある時点から」、g（x）がc * f（x）よりも小さい場合にO（f（x））であると言われます。ここで、cは定数です。
他の定義も同様で、シータはg（x）がf（x）の2つの定数倍数の間にあることを要求し、オメガはg（x）> c * f（x）を要求し、小さなバージョンはこれがすべてのそのようなものに当てはまることを要求します定数。
しかし、たとえば、アルゴリズムの実行時間がO（n ^ 2）であると言うのはなぜ興味深いのでしょうか。
これは主に、理論計算機科学では、アルゴリズムが大きな入力に対してどのように動作するかに最も関心があるため、興味深いものです。これは、入力が小さい場合、アルゴリズムの実行時間は、実装、コンパイル、ハードウェアなど、アルゴリズムを理論的に分析するときにあまり面白くないものによって大きく異なる可能性があるためです。
ただし、成長率は通常、アルゴリズムの性質によって異なります。アルゴリズムを改善するには、解決しようとしている問題についてより深い洞察が必要です。これは、たとえば、ソートアルゴリズムの場合で、単純なアルゴリズム（バブルソート）をO（n ^ 2）で実行できますが、これをO（n log n）に改善するには、真に新しいアイデアが必要です。 、マージソートまたはヒープソートで導入されたものなど。
一方、正確に5n秒で実行されるアルゴリズムと、1000n秒で実行されるアルゴリズム（たとえば、n = 3の場合の長いあくびと打ち上げ休憩の違い）がある場合は、 n = 1000000000000、スケールの違いはそれほど重要ではないようです。ただし、O（log n）を使用するアルゴリズムを使用している場合は、log（1000000000000）= 12秒待機する必要があります。これは、定数がいくら大きくても、ほぼ317、098年ではなく、定数を掛けたものになる可能性があります。つまり、完全に異なるスケールです。
これにより、状況が少し明確になることを願っています。あなたの研究で頑張ってください！