Нашр шудааст дар

Big O дар JavaScript

Муаллифон

Нотатсияи Big O

Нотатсияи Big O, ки дар маҷмӯъ номи нотатсияи Бачман-Ландау ё нотатсияи асимптотикӣ дорад, роҳест барои тавсифи иҷрои алгоритм. Он барои тавсифи ҳолати бадтарин (worst-case) алгоритм истифода мешавад. Он барои муқоисаи иҷрои алгоритмҳои гуногун истифода мешавад. Он амалигардонии алгоритмро аз рӯи андозаи воридӣ тавсиф мекунад.

Нотатсияи Big O функсияҳоро аз рӯи суръати афзоиши онҳо тавсиф мекунад: вазифаҳо бо суръати афзоиши яксон ба ҳисоб мераванд, ки аз як тартиб мебошанд. Ин як нотатсияи математикист, ки рафтори маҳдуди функсияро ҳангоми наздик шудани аргумент ба арзиши муайян ё бениҳоят тавсиф мекунад. Он барои ҷудо кардани алгоритмҳо аз рӯи он ки чӣ гуна вақти иҷро ё талаботи фазо бо афзоиши андозаи воридӣ афзоиш меёбанд, истифода мешавад. Ҳарфи O истифода мешавад, зеро суръати афзоиши функсияро ҳам тартиби он меноманд.

Такрор

Ҳалқаи For

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

Коди боло n маротиба иҷро мешавад. Мураккабии вақти ин код O(n) аст.

Ҳалқаи While

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

Коди боло n маротиба иҷро мешавад. Мураккабии вақти ин код O(n) аст.

Ҳалқаи Do While

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

Коди боло n маротиба иҷро мешавад. Мураккабии вақти ин код O(n) аст.

Такрори

Факториал

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

Коди боло n маротиба иҷро мешавад. Мураккабии вақти ин код O(n) аст.

Фибоначчи

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

Коди боло n маротиба иҷро мешавад. Мураккабии вақти ин код O(n) аст.

Ҷустуҷӯ

Ҷустуҷӯи хаттӣ

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

Коди боло n маротиба иҷро мешавад. Мураккабии вақти ин код O(n) аст.

Ҷустуҷӯи дуӣ

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
}

Коди боло log(n) маротиба иҷро мешавад. Мураккабии вақти ин код O(log(n)) аст.

Ҷобаҷокунӣ

Ҷобаҷокунии ҳавоӣ

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
}

Коди боло n^2 маротиба иҷро мешавад. Мураккабии вақти ин код O(n^2) аст.

Ҷобаҷокунии интихобӣ

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
}

Коди боло n^2 маротиба иҷро мешавад. Мураккабии вақти ин код O(n^2) аст.

Ҷобаҷокунии ҷойгиршавӣ

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
}

Коди боло n^2 маротиба иҷро мешавад. Мураккабии вақти ин код O(n^2) аст.

Ҷобаҷокунии муттаҳидшавӣ

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
}

Коди боло n log(n) маротиба иҷро мешавад. Мураккабии вақти ин код O(n log(n)) аст.

Ҷобаҷокунии зуд

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
}

Коди боло n log(n) маротиба иҷро мешавад. Мураккабии вақти ин код O(n log(n)) аст.

Маслиҳатҳо барои Big O

  • Амалиётҳои ҳисобӣ доимӣ мебошанд.
  • Таъйини арзиш ба тағйирёбанда доимӣ аст.
  • Дастрасӣ ба унсурҳои массив (аз рӯи индекс) ё объект (аз рӯи калид) доимӣ аст.
  • Дар ҳалқа, мураккабӣ дарозии ҳалқа зарб дар мураккабии он чизест, ки дар дохили ҳалқа рух медиҳад.

Манбаъҳо

Муҳокима дар Twitter

БАҲР