時間計算量：コンピュータサイエンスにおけるアルゴリズムの時間計算量は、アルゴリズムの実行時間を定性的に記述する関数ですが、プログラムが問題を解決するのにどれくらいの時間がかかるかを示すものではありません。問題の規模が大きくなるとき、プログラムに必要な時間がどれだけ早く増加するかを示しています。
つまり、高速でデータを処理するコンピュータにとって、特定のデータを処理する効率はプログラムの良し悪しを測る基準にはならず、そのデータの規模が数百倍に増えたときに、プログラムの実行時間が同じであるか、あるいは数百倍遅くなるか、または数万倍遅くなるかを見るべきです。データがどれだけ大きくても、プログラムが処理にかかる時間が常に同じであれば、そのプログラムは非常に良いものであり、O (1) の時間計算量を持つといいます。これは定数級の計算量とも呼ばれます。データの規模がどれだけ大きくなっても、かかる時間が長くなる場合、そのプログラムの時間計算量は O (n) です。例えば、n 個の数の中から最大値を見つける場合です。一方、バブルソートや挿入ソートなどは、データが 2 倍になると時間が 4 倍遅くなるため、O (n^2) の計算量に属します。また、いくつかの全探索型アルゴリズムは、必要な時間が幾何級数的に増加するため、O (a^n) の指数級計算量、さらには O (n!) の階乗級計算量になります。
O(2n^2) の計算量は存在しません。なぜなら、前の「2」は係数であり、プログラム全体の時間の増加には影響を与えないからです。同様に、O (n^3+n^2) の計算量は O (n^3) の計算量と同じです。したがって、O (0.01n^3) のプログラムの効率は O (100*n^2) の効率よりも低いといえます。n が非常に小さいときは前者が後者より優れていますが、後者の時間はデータの規模が増加するにつれて遅くなり、最終的に O (n^3) の計算量は O (n^2) を大きく上回ります。また、O (n^{100}) の計算量は O (1.01^n) の計算量よりも小さいといえます。
前述のいくつかの計算量は 2 つのレベルに分けられます。そのうち後者の計算量は、いかなる場合でも前者を大きく上回ります。一つは O (1)、O (log (n))、O (n^a) などで、これを多項式級の計算量と呼びます。なぜなら、その規模 n が底の位置に現れるからです。もう一つは O (a^n) および O (n!) 型の計算量で、これは非多項式級であり、その計算量はコンピュータが耐えられないことが多いです。問題を解決する際に選択するアルゴリズムは通常、多項式級の計算量である必要があります。非多項式級の計算量は必要な時間が非常に多く、しばしばタイムアウトします。データの規模が非常に小さい場合を除いて。