オーダー記法
処理対象のデータの件数nに対してそのアルゴリズムの実行時間がどれだけ変化するかを表す
対数を理解する必要がある
O(1)
処理時間が入力サイズに依存しない
ハッシュ探索
code:js
function accessElement(array, index) {
return arrayindex; // O(1)
}
O(\log n) O(\log_2 n) 、
処理時間が n の対数に比例して増加。
バイナリーサーチなど
二分探索
code:js
function binarySearch(array, target) {
let left = 0, right = array.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arraymid === target) return mid;
else if (arraymid < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
while文を使うようなとき
O(n)
処理時間が入力サイズに比例して増加
配列の全要素の合計を計算する
線形探索
code:js
function sumArray(array) {
let sum = 0;
for (let i = 0; i < array.length; i++) {
sum += arrayi;
}
return sum; // O(n)
}
ループ処理など
O(n \log n)
n に比例しつつ、さらに \log n の要素が加わる
クイックソート、マージソートとかはこれ
code:js
function quickSort(array) {
if (array.length <= 1) return array;
const pivot = array0;
const left = array.slice(1).filter(x => x < pivot);
const right = array.slice(1).filter(x => x >= pivot);
return ...quickSort(left), pivot, ...quickSort(right);
}
O(n^2)
処理時間が入力サイズの2乗に比例
多重ループ（二重ループ）
バブルソート、選択ソート、挿入ソート
code:js
function findPairs(array) {
for (let i = 0; i < array.length; i++) {
for (let j = i + 1; j < array.length; j++) {
console.log(arrayi, arrayj); // O(n^2)
}
}
}
O(2^n)
処理時間が入力サイズの指数に比例して増加
再帰処理など
code:js
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2); // O(2^n)
}
O(n!)
処理時間が入力サイズの階乗に比例して増加
全順列を生成するなど
これが一番計算量がアカン
というかデータの量によっては現在のコンピュータでも計算にとんでもない時間がかかる
https://www.youtube.com/watch?v=Q4gTV4r0zRs
これじゃん
フカシギの数え方
#アルゴリズム