Python アルゴリズムの時間計算量

アルゴリズムを実装する場合、アルゴリズムの複雑さは通常、時間の複雑さと空間の複雑さという 2 つの側面から考慮されます。名前が示すように、時間計算量はアルゴリズムの計算負荷を測定するために使用され、空間計算量はアルゴリズムによって占有されるメモリ空間を測定するために使用されます。

[[282694]]

この記事では、時間計算量の概念から始めて、実際のコード例を使用してアルゴリズムの時間計算量を分析します。

漸近的時間計算量

時間計算量とは、アルゴリズム操作に要する時間のことです。入力データのサイズによってアルゴリズムの所要時間が異なるため、アルゴリズムの実行時間を評価するのは困難です。そのため、通常は時間頻度、つまりアルゴリズムが計算操作を実行する回数に注目します。これは T(n) と表され、n は問題のサイズと呼ばれます。

同様に、n は変数であるため、n が変化すると、時間周波数 T(n) も変化します。時間計算量の限界ケースをアルゴリズムの漸近的時間計算量と呼び、O(n) と表記されます。これには関数の低次係数と主要係数は含まれません。

次の例で説明してみましょう。

上記の例と同様に、コードの平均実行時間の仮定に基づいて、run_time(n) 関数の時間計算量を次のように計算します。

上記の時間計算量計算式 T(n) は、関数 run_time(n) の時間計算量の推定値です。 n の値が非常に大きい場合、T(n) 関数の定数項 time0 と n の係数 (time1+time2+time3+time4) が n に与える影響は無視できるため、ここでの関数 run_time(n) の時間計算量は O(n) として表すことができます。

極端な状態（たとえば、n が非常に大きい）で時間計算量を計算するため、次の 2 つの特性があります。

• 低次の項の影響は高次の項に比べて非常に小さいため、無視できます。
• 最高項係数が最高項に与える影響も非常に小さいため、無視できます。

上記の 2 つの特性に応じて、時間の計算量は次のように計算されます。

1. 最高次の項のみを取り、低次の項を破棄します。

2. 最高項の係数を削除します。

3. 定数順序の場合、時間計算量はO(1)とする。

次の例を通して、一般的な時間計算量を理解しましょう。

時間計算量: 定数次数 O(1)

時間計算量: 線形順序 O(n)

時間計算量: 線形順序 O(n)

時間計算量: 平方次数 O(n^2)

時間計算量: 平方次数 O(n^2)

時間計算量: 平方次数 O(n^2)

時間計算量: 3次O(n^3)

時間計算量: 対数オーダー O(logn)

問題のサイズ n が大きくなるにつれて、上記の時間計算量が増加し、アルゴリズムの実行効率が低下します。時間計算量は次のようにランク付けされます。

練習する

次の count_sort 関数はカウントソートを実装します。リスト内の数字の範囲は 0 から 100 までで、リストの長さは約 100 万です。

上記の count_sort 関数の空間計算量は O(n) であり、式は次のようになります。