Objavljeno

Veliki O u JavaScript-u

Autori

Velika O notacija

Velika O notacija, kolektivno nazvana Bachmann-Landau notacija ili asimptotska notacija, je način opisivanja performansi algoritma. Koristi se za opisivanje najgoreg scenarija algoritma. Koristi se za usporedbu performansi različitih algoritama. Opisuje implementaciju algoritma u odnosu na veličinu unosa.

Velika O notacija karakterizira funkcije prema njihovim stopama rasta: zadaci s istom stopom rasta smatraju se istim redom. To je matematička notacija koja opisuje granično ponašanje funkcije kada argument teži određenoj vrijednosti ili beskonačnosti. Koristi se za klasificiranje algoritama prema tome kako se njihovo vrijeme izvođenja ili zahtjevi za prostorom povećavaju kako se veličina unosa povećava. Slovo O se koristi jer se stopa rasta funkcije također naziva njenim redom.

Iteracija

Petlja for

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

Gornji kod će se izvršiti n puta. Složenost vremena ovog koda je O(n).

Petlja while

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

Gornji kod će se izvršiti n puta. Složenost vremena ovog koda je O(n).

Petlja do while

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

Gornji kod će se izvršiti n puta. Složenost vremena ovog koda je O(n).

Rekurzija

Faktorijel

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

Gornji kod će se izvršiti n puta. Složenost vremena ovog koda je O(n).

Fibonacci

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

Gornji kod će se izvršiti n puta. Složenost vremena ovog koda je O(n).

Pretraživanje

Linearno pretraživanje

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

Gornji kod će se izvršiti n puta. Složenost vremena ovog koda je O(n).

Binarno pretraživanje

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
}

Gornji kod će se izvršiti log(n) puta. Složenost vremena ovog koda je O(log(n)).

Sortiranje

Mjehurićno sortiranje

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
}

Gornji kod će se izvršiti n^2 puta. Složenost vremena ovog koda je O(n^2).

Sortiranje selekcijom

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
}

Gornji kod će se izvršiti n^2 puta. Složenost vremena ovog koda je O(n^2).

Sortiranje umetanjem

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
}

Gornji kod će se izvršiti n^2 puta. Složenost vremena ovog koda je O(n^2).

Spajanje sortiranjem

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
}

Gornji kod će se izvršiti n log(n) puta. Složenost vremena ovog koda je O(n log(n)).

Brzo sortiranje

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
}

Gornji kod će se izvršiti n log(n) puta. Složenost vremena ovog koda je O(n log(n)).

Savjeti za Veliku O notaciju

  • Aritmetičke operacije su konstantne
  • Dodela promenljivih je konstantna
  • Pristup elementima niza (po indeksu) ili objekta (po ključu) je konstantan
  • U petlji, složenost je dužina petlje puta složenost onoga što se događa unutar petlje

Resursi

Raspravljajte na Twitteru

DIJELI