データ構造とアルゴリズム
コーディング面接対策をしている中ですっきりと理解できない概念があったのでそれをまとめさせていただいます。
コーディング面接において注視されるのが、アルゴリズムの計算量とメモリ量が最適であるか。ということ。それを表したものが下記2点である。
・時間計算量(Runtime Complexity)
・空間計算量(Space Complexity)
時間計算量(Runtime Complexity)
アルゴリズムが入力サイズnに対してどれくらいの時間（計算ステップ数）がかかるかを表します。
通常、下記のようにBig-O記法 で表されます。
| 計算量 | Big-O | 例 |
|---|---|---|
| 定数時間 | O(1) | 配列の要素を1つ取得（ arr[i] ） |
| 対数時間 | O(log n) | 二分探索 |
| 線形時間 | O(n) | 配列を1回ループする |
| 線形対数時間 | O(n log n) | クイックソート、マージソート |
| 二次時間 | O(n2乗) | ネストしたループ(バブルソート) |
| 指数時間 | O(2n乗) | 再帰的な組み合わせ探索（ナイーブなフィボナッチ計算） |
| 階乗時間 | O(n!) | 全順列の探索（巡回セールスマン問題の全探索） |
0(n)の例 -配列の要素の合計を計算 ↓
int sum(int[] nums){
int total = 0;
for (int num : nums){
total += num;
}
return total;
}
→配列の長さnに比例してループ回数が増えるので O(n)。
0(n2乗)の例 -2重ループ ↓
void printPairs(int[] arr) {
for (int i = 0; i < arr.length; i++){
for (int j = 0; j < arr.length;j++) {
System.out.println(arr[i] + ", " + arr[j]);
}
}
}
→二重ループなので O(n²)。
空間計算量（Space Complexity)
アルゴリズムが使うメモリ量を入力サイズnの関数として表し、入力サイズnに対して、追加のメモリをどれだけ使うか を評価します。
※追加のメモリ
→ 入力とは別に確保するメモリのこと
| 空間計算量 | Big-O | 例 |
|---|---|---|
| 定数空間 | O(1) | 追加のメモリを使わない |
| 線形空間 | O(n) | 配列やリストを作る |
| 二次空間 | O(n2乗) | 2D配列を使う |
| 指数空間 | O(2n乗) | 再起的なバックトラッキング |
例 O(1)の空間計算量
int findMax(int[] arr) {
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
return max;
}
→ 配列とは別に変数 max しか使っていないので O(1)。
O(n)の空間計算量
List<Integer> numsList(int[] arr){
List<Integer> newList = new ArrayList<>();
for(int num : arr){
newList.add(num);
}
return newList;
}
→ 入力サイズnに比例して新しいリストができるので O(n)。
まとめ
・時間計算量は「処理時間が入力サイズに対してどれくらい増えるか」
・空間計算量は「追加のメモリがどれくらい必要か」