Waxaa la daabacay

Big O ee JavaScript

Qorayaasha

Calaamadda O Weyn, Qoraalka Bachmann-Landau ama Calaamadda Asymptotic

Calaamadda O Weyn, oo si wada jir ah loogu yeero qoraalka Bachmann-Landau ama calaamadda asymptotic, waa hab lagu sharaxayo waxqabadka algorithm. Waxaa loo isticmaalaa in lagu sharaxo xaaladda ugu xun ee algorithm. Waxaa loo isticmaalaa in lagu barbar dhigo waxqabadka algorithms kala duwan. Waxay sharaxaysaa fulinta algorithm marka loo eego cabbirka gelitaanka.

Calaamadda O Weyn waxay qeexaysaa hawlaha iyadoo loo eegayo heerarka korriinka: hawlaha leh heerka korriinka la mid ah waxaa loo tixgeliyaa inay yihiin isla amar. Waa calaamad xisaabeed oo sharaxaysa dhaqanka xaddidan ee shaqada marka dooddu ay u janjeedho qiime gaar ah ama aan dhammaad lahayn. Waxaa loo isticmaalaa in lagu kala saaro algorithms iyadoo loo eegayo sida waqtigooda fulinta ama shuruudaha booska ay u koraan marka cabbirka gelitaanka uu koro. Xarafka O waxaa loo isticmaalaa sababtoo ah heerka korriinka shaqada sidoo kale loogu yeero amarkeeda.

Wareegga

Wareegga For

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

Koodhkan kor ku xusan wuxuu shaqeyn doonaa n jeer. Xaqiiqada wakhtiga ee koodhkan waa O(n).

Wareegga While

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

Koodhkan kor ku xusan wuxuu shaqeyn doonaa n jeer. Xaqiiqada wakhtiga ee koodhkan waa O(n).

Wareegga Do While

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

Koodhkan kor ku xusan wuxuu shaqeyn doonaa n jeer. Xaqiiqada wakhtiga ee koodhkan waa O(n).

Recursion

Factorial

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

Koodhkan kor ku xusan wuxuu shaqeyn doonaa n jeer. Xaqiiqada wakhtiga ee koodhkan waa O(n).

Fibonacci

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

Koodhkan kor ku xusan wuxuu shaqeyn doonaa n jeer. Xaqiiqada wakhtiga ee koodhkan waa O(n).

Raadista

Raadinta Linear

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

Koodhkan kor ku xusan wuxuu shaqeyn doonaa n jeer. Xaqiiqada wakhtiga ee koodhkan waa O(n).

Raadinta Binary

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
}

Koodhkan kor ku xusan wuxuu shaqeyn doonaa log(n) jeer. Xaqiiqada wakhtiga ee koodhkan waa O(log(n)).

Kala Saaridda

Kala Saaridda Bubble

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
}

Koodhkan kor ku xusan wuxuu shaqeyn doonaa n^2 jeer. Xaqiiqada wakhtiga ee koodhkan waa O(n^2).

Kala Saaridda Selection

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
}

Koodhkan kor ku xusan wuxuu shaqeyn doonaa n^2 jeer. Xaqiiqada wakhtiga ee koodhkan waa O(n^2).

Kala Saaridda Insertion

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
}

Koodhkan kor ku xusan wuxuu shaqeyn doonaa n^2 jeer. Xaqiiqada wakhtiga ee koodhkan waa O(n^2).

Kala Saaridda Merge

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
}

Koodhkan kor ku xusan wuxuu shaqeyn doonaa n log(n) jeer. Xaqiiqada wakhtiga ee koodhkan waa O(n log(n)).

Kala Saaridda Quick

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
}

Koodhkan kor ku xusan wuxuu shaqeyn doonaa n log(n) jeer. Xaqiiqada wakhtiga ee koodhkan waa O(n log(n)).

Talooyin Calaamadda O Weyn

  • Hawlgallada xisaabeed waa joogto ah
  • Assignta isbeddelka waa joogto ah
  • Helitaanka xubnaha ku jira array (iyadoo loo marayo index) ama object (iyadoo loo marayo key) waa joogto ah
  • Wareegga, xaqiiqada waa dhererka wareegga la dhuftay xaqiiqada wax kasta oo ku dhacda gudaha wareegga

Kheyraad

Kala hadal Twitter

WADAAG