- 公開日
JavaScriptにおけるビッグO記法
- 著者
- 名前
- Imamuzzaki Abu Salam
- https://x.com/ImBIOS_Dev
ビッグO記法
ビッグO記法は、バッハマン・ランダウ記法または漸近記法とも呼ばれ、アルゴリズムのパフォーマンスを記述する方法です。アルゴリズムの最悪の場合のシナリオを記述するために使用されます。さまざまなアルゴリズムのパフォーマンスを比較するために使用されます。入力サイズに基づいてアルゴリズムの実装を記述します。
ビッグO記法は、関数をその成長率に従って特徴付けます。同じ成長率を持つタスクは、同じオーダーであると見なされます。特定の値または無限大に引数が近づくときの関数の極限的な挙動を記述する数学的表記です。入力サイズが大きくなるにつれて、アルゴリズムの実行時間または空間要件がどのように増加するかを分類するために使用されます。関数の成長率はオーダーとも呼ばれるため、Oという文字が使用されます。
反復処理
forループ
for (let i = 0; i < n; i++) {
console.log(i)
}
上記のコードはn回実行されます。このコードの時間計算量はO(n)です。
whileループ
let i = 0
while (i < n) {
console.log(i)
i++
}
上記のコードはn回実行されます。このコードの時間計算量はO(n)です。
do whileループ
let i = 0
do {
console.log(i)
i++
} while (i < n)
上記のコードはn回実行されます。このコードの時間計算量はO(n)です。
再帰
階乗
function factorial(n) {
if (n === 0) {
return 1
}
return n * factorial(n - 1)
}
上記のコードはn回実行されます。このコードの時間計算量はO(n)です。
フィボナッチ数列
function fibonacci(n) {
if (n <= 1) {
return n
}
return fibonacci(n - 1) + fibonacci(n - 2)
}
上記のコードはn回実行されます。このコードの時間計算量はO(n)です。
検索
線形探索
function linearSearch(arr, value) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === value) {
return i
}
}
return -1
}
上記のコードはn回実行されます。このコードの時間計算量はO(n)です。
二分探索
function binarySearch(arr, value) {
let start = 0
let end = arr.length - 1
let middle = Math.floor((start + end) / 2)
while (arr[middle] !== value && start <= end) {
if (value < arr[middle]) {
end = middle - 1
} else {
start = middle + 1
}
middle = Math.floor((start + end) / 2)
}
if (arr[middle] === value) {
return middle
}
return -1
}
上記のコードはlog(n)回実行されます。このコードの時間計算量はO(log(n))です。
ソート
バブルソート
function bubbleSort(arr) {
for (let i = arr.length; i > 0; i--) {
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
上記のコードはn^2回実行されます。このコードの時間計算量はO(n^2)です。
選択ソート
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let lowest = i
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[lowest]) {
lowest = j
}
}
if (i !== lowest) {
let temp = arr[i]
arr[i] = arr[lowest]
arr[lowest] = temp
}
}
return arr
}
上記のコードはn^2回実行されます。このコードの時間計算量はO(n^2)です。
挿入ソート
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let currentVal = arr[i]
for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
arr[j + 1] = arr[j]
}
arr[j + 1] = currentVal
}
return arr
}
上記のコードはn^2回実行されます。このコードの時間計算量はO(n^2)です。
マージソート
function mergeSort(arr) {
if (arr.length <= 1) return arr
let mid = Math.floor(arr.length / 2)
let left = mergeSort(arr.slice(0, mid))
let right = mergeSort(arr.slice(mid))
return merge(left, right)
}
function merge(left, right) {
let results = []
let i = 0
let j = 0
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
results.push(left[i])
i++
} else {
results.push(right[j])
j++
}
}
while (i < left.length) {
results.push(left[i])
i++
}
while (j < right.length) {
results.push(right[j])
j++
}
return results
}
上記のコードはn log(n)回実行されます。このコードの時間計算量はO(n log(n))です。
クイックソート
function pivot(arr, start = 0, end = arr.length + 1) {
let pivot = arr[start]
let swapIdx = start
function swap(array, i, j) {
let temp = array[i]
array[i] = array[j]
array[j] = temp
}
for (let i = start + 1; i < arr.length; i++) {
if (pivot > arr[i]) {
swapIdx++
swap(arr, swapIdx, i)
}
}
swap(arr, start, swapIdx)
return swapIdx
}
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left < right) {
let pivotIndex = pivot(arr, left, right)
quickSort(arr, left, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, right)
}
return arr
}
上記のコードはn log(n)回実行されます。このコードの時間計算量はO(n log(n))です。
ビッグOのヒント
- 算術演算は定数です。
- 変数代入は定数です。
- 配列（インデックスによる）またはオブジェクト（キーによる）の要素へのアクセスは定数です。
- ループでは、計算量はループの長さに、ループ内で実行される処理の計算量を掛けたものになります。