Ýaýradylan senesi

JavaScript-da Big O

Awtorlar

Big O Belligi, Assimptotik Belligi

Big O Belligi, umumylykda Bachmann-Landau belligi ýa-da assimptotik belligi diýlip atlandyrylýar, algoritmiň işlemegiň tizligini beýan etmek üçin ulanylýan bir usuldyr. Ol algoritmiň iň ýaramaz ýagdaýyny beýan etmek üçin ulanylýar. Ol dürli algoritmleriň işlemegiň tizligini deňeşdirmek üçin ulanylýar. Ol algoritmiň durmuşa geçirilmegini giriş ölçegine görä beýan edýär.

Big O belligi funksiýalary öz ösüş tizligine görä häsiýetlendirýär: Birnäçe ösüş tizligine eýe bolan işler bir tarapdan bir bölek hasaplanýar. Bu, bir funksiýanyň argument özüne degişli bir gymmata ýa-da çäksizlige tarap ýören wagtynda, funksiýanyň çäklendiriji hereketini beýan edýän matematik bir belgidir. Algoritmleriň işleme wagtynyň ýa-da ýer talaplarynyň giriş ölçeg ösen wagtynda nähili ösýändigini bölmek üçin ulanylýar. "O" harpy ulanylýar, sebäbi funksiýanyň ösüş tizligi onuň tertibi diýlip hem atlandyrylýar.

Yterasiýa

For Döwrü

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

Ýokarda görkezilen kod n gezek işlär. Bu kodyň wagtyň çylşyrymlylygy O(n) -dir.

While Döwrü

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

Ýokarda görkezilen kod n gezek işlär. Bu kodyň wagtyň çylşyrymlylygy O(n) -dir.

Do While Döwrü

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

Ýokarda görkezilen kod n gezek işlär. Bu kodyň wagtyň çylşyrymlylygy O(n) -dir.

Rekursiýa

Faktorial

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

Ýokarda görkezilen kod n gezek işlär. Bu kodyň wagtyň çylşyrymlylygy O(n) -dir.

Fibonaççi

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

Ýokarda görkezilen kod n gezek işlär. Bu kodyň wagtyň çylşyrymlylygy O(n) -dir.

Gözleg

Liner Gözleg

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

Ýokarda görkezilen kod n gezek işlär. Bu kodyň wagtyň çylşyrymlylygy O(n) -dir.

Iki Terfli Gözleg

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
}

Ýokarda görkezilen kod log(n) gezek işlär. Bu kodyň wagtyň çylşyrymlylygy O(log(n)) -dir.

Sortlamak

Püzürle Sortlamak

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
}

Ýokarda görkezilen kod n^2 gezek işlär. Bu kodyň wagtyň çylşyrymlylygy O(n^2) -dir.

Saýlap Sortlamak

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
}

Ýokarda görkezilen kod n^2 gezek işlär. Bu kodyň wagtyň çylşyrymlylygy O(n^2) -dir.

Goşmaça Sortlamak

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
}

Ýokarda görkezilen kod n^2 gezek işlär. Bu kodyň wagtyň çylşyrymlylygy O(n^2) -dir.

Birleşdirme Sortlamak

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
}

Ýokarda görkezilen kod n log(n) gezek işlär. Bu kodyň wagtyň çylşyrymlylygy O(n log(n)) -dir.

Tiz Sortlamak

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
}

Ýokarda görkezilen kod n log(n) gezek işlär. Bu kodyň wagtyň çylşyrymlylygy O(n log(n)) -dir.

Big O üçin maslahatlar

  • Aritmetik işlemler sabitdir.
  • Ýer bölüwi sabitdir.
  • Massiwiň (indekse görä) ýa-da obýektiň (açara görä) elementine ýetmek sabitdir.
  • Döwrüň içindäki döwrüň uzynlygy döwrüň içinde bolýan zatlaryň çylşyrymlylygynyň köpeltgisidir.

Goşmaça maglumatlar

Twitterde ara alyp maslahatlaşmak

PAÝLAŞ