Weşand li ser

Big O li JavaScript

Nivîskar

Notasyona Bachmann-Landau anku Notasyona Asymptotic

Notasyona Bachmann-Landau, ku bi hev re dibêjin notasyona Bachmann-Landau yan jî notasyona asymptotic, awayek ji bo ravekirina karîgeriya algoritmayek e. Ew tê bikaranîn ji bo ravekirina rewşa herî xirab a algoritmayek. Ew tê bikaranîn ji bo berhevdanîna karîgeriya algoritmayên cuda. Ew pêkanîna algoritmayek li gorî mezinahiya inputê rave dike.

Notasyona Big O fonksiyonan li gorî rêjeya wan a mezinbûnê diyar dike: erkên ku heman rêjeya mezinbûnê heye, wekî heman rêzê tên hesibandin. Ev notasyoneke matematîkî ye ku tevgera sînorî ya fonksiyonê diyar dike dema ku arguman ber bi nirxek taybetî yan jî bêdawî ve diçe. Ew tê bikaranîn ji bo dabeşkirina algoritmayan li gorî ka daxwazên dem an jî cîhê wan çawa mezin dibin dema ku mezinahiya inputê mezin dibe. Tîpa O tê bikaranîn ji ber ku rêjeya mezinbûnê ya fonksiyonê wekî rêza wê jî tê binavkirin.

Iterasyon

For Loop

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

Kodeya jorîn n caran dê were gerandin. Pîvana tevliheviya demê ya vê kodeyê O(n) e.

While Loop

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

Kodeya jorîn n caran dê were gerandin. Pîvana tevliheviya demê ya vê kodeyê O(n) e.

Do While Loop

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

Kodeya jorîn n caran dê were gerandin. Pîvana tevliheviya demê ya vê kodeyê O(n) e.

Recursion

Factorial

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

Kodeya jorîn n caran dê were gerandin. Pîvana tevliheviya demê ya vê kodeyê O(n) e.

Fibonacci

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

Kodeya jorîn n caran dê were gerandin. Pîvana tevliheviya demê ya vê kodeyê O(n) e.

Lêgerîn

Lêgerîna Xetî

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

Kodeya jorîn n caran dê were gerandin. Pîvana tevliheviya demê ya vê kodeyê O(n) e.

Lêgerîna Binêrî

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
}

Kodeya jorîn log(n) caran dê were gerandin. Pîvana tevliheviya demê ya vê kodeyê O(log(n)) e.

Rêzkirin

Rêzkirina Hûrikê

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
}

Kodeya jorîn n^2 caran dê were gerandin. Pîvana tevliheviya demê ya vê kodeyê O(n^2) e.

Rêzkirina Hilbijartinê

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
}

Kodeya jorîn n^2 caran dê were gerandin. Pîvana tevliheviya demê ya vê kodeyê O(n^2) e.

Rêzkirina Derxistinê

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
}

Kodeya jorîn n^2 caran dê were gerandin. Pîvana tevliheviya demê ya vê kodeyê O(n^2) e.

Rêzkirina Hevgirtinê

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
}

Kodeya jorîn n log(n) caran dê were gerandin. Pîvana tevliheviya demê ya vê kodeyê O(n log(n)) e.

Rêzkirina Bilez

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
}

Kodeya jorîn n log(n) caran dê were gerandin. Pîvana tevliheviya demê ya vê kodeyê O(n log(n)) e.

Pêşniyarên Ji Bo Big O

  • Operasyonên aritmetîkî sabit in
  • Têkilîya guherbarê sabit e
  • Gihîştina elementên rêze (bi nîşan) an jî tiştan (bi key) sabit e
  • Di nav loopê de, tevlihevî dirêjahiya loopê caran tevliheviya tiştê ku di nav loopê de diqewime ye

Çavkanî

Li ser Twitter nîqaş bike

Parve bike