Big O jelölés JavaScriptben

A Big O Notation, összefoglaló néven Bachmann-Landau jelölés vagy aszimptotikus jelölés, egy módszer az algoritmus teljesítményének leírására. Egy algoritmus legrosszabb forgatókönyvének leírására szolgál. Különböző algoritmusok teljesítményének összehasonlítására szolgál. Egy algoritmus megvalósítását írja le a bemeneti méret alapján.

A Big O jelölés a függvényeket növekedési ütemük szerint jellemzi: az azonos növekedési ütemű feladatokat azonos sorrendűnek tekintjük. Ez egy matematikai jelölés, amely leírja egy függvény korlátozó viselkedését, amikor az argumentum egy adott érték vagy végtelen felé irányul. Az algoritmusok osztályozására szolgál aszerint, hogy a bemeneti méret növekedésével hogyan nő a futási idő- vagy helyigényük. Az O betűt azért használjuk, mert egy függvény növekedési ütemét a sorrendjének is nevezik.

Ismétlés

A hurokhoz

for (let i = 0; i < n; i++) {
 console.log(i)
}

A fenti kód n-szer fut le. Ennek a kódnak az időbonyolultsága O(n).

Míg hurok

let i = 0
while (i < n) {
 console.log(i)
 i++
}

A fenti kód n-szer fut le. Ennek a kódnak az időbonyolultsága O(n).

Do while ciklus

let i = 0
do {
 console.log(i)
 i++
} while (i < n)

A fenti kód n-szer fut le. Ennek a kódnak az időbonyolultsága O(n).

Rekurzió

Faktoriális

function factorial(n) {
 if (n === 0) {
 return 1
 }
 return n * factorial(n - 1)
}

A fenti kód n-szer fut le. Ennek a kódnak az időbonyolultsága O(n).

Fibonacci

function fibonacci(n) {
 if (n <= 1) {
 return n
 }
 return fibonacci(n - 1) + fibonacci(n - 2)
}

A fenti kód n-szer fut le. Ennek a kódnak az időbonyolultsága O(n).

Keresés

Lineáris keresés

function linearSearch(arr, value) {
 for (let i = 0; i < arr.length; i++) {
 if (arr[i] === value) {
 return i
 }
 }
 return -1
}

A fenti kód n-szer fut le. Ennek a kódnak az időbonyolultsága O(n).

Bináris keresés

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
}

A fenti kód log(n) alkalommal fog lefutni. Ennek a kódnak az időbonyolultsága O(log(n)).

Válogatás

Buborékos fajta

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
}

A fenti kód n²-szer fut le. Ennek a kódnak az időbonyolultsága O(n²).

Kijelölés rendezése

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
}

A fenti kód n²-szer fut le. Ennek a kódnak az időbonyolultsága O(n²).

Beillesztési rendezés

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
}

A fenti kód n²-szer fut le. Ennek a kódnak az időbonyolultsága O(n²).

Összevonás rendezés

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
}

A fenti kód n log(n) alkalommal fog lefutni. Ennek a kódnak az időbonyolultsága O(n log(n)).

Gyors rendezés

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
}

A fenti kód n log(n) alkalommal fog lefutni. Ennek a kódnak az időbonyolultsága O(n log(n)).

Tippek Big O számára

- Az aritmetikai műveletek állandóak
- A változók hozzárendelése állandó
- A tömbben (index alapján) vagy objektumban (kulcsonként) lévő elemek elérése állandó
- A hurokban a komplexitás a hossza a ciklus szorzata a hurkon belüli események összetettségével

Erőforrások

- [Big O Cheat Sheet](https://www.bigocheatsheet.com/)
- [Big O Notation](https://www.interviewcake.com/article/javascript/big-o -notation-time-and-space-complexity)
- [Big O Notation](https://www.freecodecamp.org/news/big-o-notation-time-and-space-complexity- Példákkal magyarázva-1f6e26a13a6e/)