PS：近日、WeChat 公式号のトラフィックオーナーの開設条件が、元々5000 人のファンから 500 人のファンに引き下げられました。WeChat のスローガンは「小さな個体でも独自のブランドを持っている」ということを覚えています。以前は公式アカウントを開設することに躊躇していた人々も、今後は開設するでしょう。もちろん、Tencent がこれを行うのは、現在の公式アカウントの開封率が非常に低いためであり、また、Baidu、Toutiao などの情報フィードに対抗する必要があるためです。
時間複雑度と空間複雑度は、具体的なプラットフォームに基づいて適切なアルゴリズムを選択するためのヒントとなります。時間と空間を交換する設計思想を学ぶ必要があります。たとえば、マイコンなどではメモリスペースが制約されているため、最適なアルゴリズムを追求する際には、時間を空間に変換して設計することができます。もちろん、大容量のデバイスでは、最適なアルゴリズムを設計するために時間を空間に変換する設計思想を選択することができます。したがって、時間複雑度と空間複雑度は、一定の制約条件の下で、特定のアルゴリズムやコードブロックの実行速度を判断するための方法です。時間と空間の複雑度については、次のいくつかの側面を理解し学習する必要があります。
- データ構造とアルゴリズムの関係
- 時間複雑度
- 空間複雑度
- 結論
データ構造とアルゴリズムの関係
データ構造は、データの格納方法を指し、アルゴリズムはデータを操作する方法の集まりです。したがって、データ構造はアルゴリズムにサービスを提供し、アルゴリズムは特定のデータ構造に作用します。
大 O 記法
大 O 記法は、コードの実行時間効率を大まかに理解するためのものです。たとえば、次のコード：
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
有効なコード（代入操作がある）の各行の実行時間が 1 単位時間であると仮定すると、上記のコードの実行時間は 2n + 2 単位時間です。ここでわかるように、コードの実行時間は、各行の有効なコードの実行回数に比例します。
もし次のコードだったら：
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
上記のコードの実行時間は 2n*n + 2n + 3 単位時間です。ここでも、コードの実行時間は、各行の有効なコードの実行回数に比例します。次の式で表すこともできます。
T(n) = O(n)
したがって、上記の 2 つのコードの実行時間とコードの実行回数の関係は次のように表されます。
T(n) = O(2n + 2)
T(n) = O( 2n*n + 2n + 3)
データの規模が増大するにつれて、後半の定数項はデータの規模の変化の傾向に影響を与えません。上記の 2 つの関数のうち、1 つは明らかに線形関数であり、もう 1 つは 2 次関数です。データの規模が増大するにつれて、最終的に 2 次関数の値が 1 次関数を超えるため、最高次数を比較するために他の項目を除外して簡略化することができます。
T(n) = O(n)
T(n) = O(n*n)
上記の 2 つのコードの時間複雑度は、大 O 記法で O (n) と O (n*n) と表されます。
時間複雑度
時間複雑度は、上記の結論からわかるように、コードの実行時間がデータの規模の変化に従ってどのように変化するかを表します。時間複雑度の分析では、データの規模が増大するにつれて、最も大きなオーダーの時間複雑度に注目することが重要です。
一般的な時間複雑度のオーダーは次のようになります。
定数オーダー(O(1)) < 対数オーダー(O(logn)) < 線形オーダー(n) < 線形対数オーダー(O(nlogn)) < 二次オーダー(O(n^2)) < 三次オーダー(O(n^3)) < 階乗オーダー(O(n!)) < n乗オーダー(O(n^n))
上記のオーダーの中で、階乗オーダーや n 乗オーダーは多項式オーダーではなく、データの規模が急速に増大すると、非常に長い時間がかかるようになります。このようなアルゴリズムは、効率が最も低いアルゴリズムです。以下では、多項式オーダーの注意点について説明します。
O (n)：コードの行数に関係なく、実行回数が確定している場合、その時間複雑度のオーダーは O (1) となり、O (2)、O (3) などの他の場合は発生しません。
O (logn)：対数時間複雑度の計算は、条件を満たすためにコードが実行される回数を計算することに主眼が置かれています。例えば、次のコード：
i=1;
while (i <= n) {
i = i * 2;
}
上記のコードでは、コードが実行される回数を計算するだけで十分です。つまり、コードが完了するまでに何回実行する必要があるかを見つけるだけで十分です。つまり、i の値は 1、2、8、16 などであり、2^0、2^1、2^3、2^4 などです。したがって、i と n の関係は 2^t = n であり、t の値を計算し、関係のない項目を削除して時間複雑度を計算することができます。もちろん、線形対数オーダー O (nlogn) は、上記のコードを n 回ループする結果です。
O (m+n)：次のコードのように、時間複雑度を表す場合、直接に足し合わせて最高次数を取ることはできません。
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
m と n は 2 つのデータの規模を表し、どちらが大きいかはわかりません。この場合、時間複雑度は O (m) + O (n) と表されます。sum_1 * sum_2 の場合、対応する時間複雑度は O (m) * O (n) と表されます。
時間複雑度の分析は基本的には上記のようなものですが、次に特殊なケースの複雑度分析を見ていきます。次のコードの時間複雑度を分析してみましょう。
// nは配列arrayの長さを表します
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) pos = i;
}
return pos;
}
分析プロセス：i と pos の代入操作は合計で 2 回ですが、コードの実行時間の変化の傾向には影響を与えませんので、無視して構いません。for ループの中では、i が m に増加すると、for ループ内の if 文の条件を満たす場合、コードの実行時間は (1+m) n と表されます。したがって、このコードの時間複雑度は必ず O (n) です。なぜなら、if 文は x と等しい値を見つけた場合でも for ループから抜け出さないからです。次のようにコードを変更すると、
// nは配列arrayの長さを表します
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
配列内で x と等しい値を見つけた場合にループを抜けるようにすると、(1+m) n という時間複雑度の場合、m は定数値であるため無視できます。この場合、このコードの時間複雑度は O (1) です。もちろん、if 文の条件を満たさない場合は、常に n 回ループするため、このコードの時間複雑度は O (n) です。同じコードでも、異なる条件下では異なる時間複雑度が発生することがわかります。このような場合、時間複雑度を 3 つに細分化することができます。
- 最良の場合の時間複雑度分析：理想的な場合にコードが実行される時間複雑度を指します。上記のコードの場合、配列内で if 文の条件を満たす値を見つけた場合、このコードの時間複雑度は O (1) です。
- 最悪の場合の時間複雑度分析：最も悪い場合にコードが実行される時間複雑度を指します。上記のコードの場合、配列内で if 文の条件を満たさない場合、このコードの時間複雑度は O (n) です。
空間複雑度
空間複雑度は、データの規模の増加に伴って必要なストレージスペースの変化の傾向を反映します。次のコードを考えてみましょう。
void print(int n) {
int i = 0;//スタックメモリ
int[] a = new int[n];//ヒープメモリ
for (i; i <n; ++i) {
a[i] = i * i;
}
}
上記のコードでは、メモリの割り当てに関連するコードは 2 か所しかなく、変数 i のメモリスペースは固定であるため、無視して構いません。配列の宣言によってメモリが割り当てられ、そのサイズは n 個の int 型のメモリサイズです。したがって、このコードの空間複雑度は O (n) です。
まとめ
時間複雑度は、コードの実行時間がデータの規模の変化に従ってどのように変化するかを反映します。特にループのネストなどに注意を払います。空間複雑度は、データの規模の増加に伴って必要なストレージスペースの変化の傾向を反映します。時間複雑度は空間複雑度よりも一般的に使用され、開発者が複雑度について話す場合、通常は時間複雑度を指します。さらに、特定のコードに対して、最良の場合の時間複雑度、最悪の場合の時間複雑度、平均時間複雑度、および償却時間複雑度に細分化することもできますが、分析のアプローチは基本的に同じです。