Yayımlanma tarixi

JavaScript-də ən böyük O nömrəsi

Müəllif(lər)

Böyük O Notasiyası

Böyük O Notasiyası, ümumiyyətlə Baçmann-Landau notasiyası və ya asimptotik notasiya olaraq adlandırılır, bir alqoritmin performansını təsvir etmək üçün istifadə olunan bir üsuldur. Bir alqoritmin ən pis hal senarisini təsvir etmək üçün istifadə olunur. Fərqli alqoritmlərin performansını müqayisə etmək üçün də istifadə olunur. Bir alqoritmin icrasını giriş ölçüsünün funksiyası olaraq təsvir edir.

Böyük O notasiyası funksiyaları onların böyümə sürətlərinə görə xarakterizə edir: eyni böyümə sürətinə malik tapşırıqlar eyni sırada olduğu hesab olunur. Müəyyən bir dəyərə və ya sonsuzluğa meyl edərkən bir funksiyanın limit davranışını təsvir edən riyazi bir notasyondur. Alqoritmləri icra vaxtı və ya yer tələbatlarının giriş ölçüsü artdıqca necə artdığına görə təsnif etmək üçün istifadə olunur. O hərfi istifadə olunur, çünki bir funksiyanın böyümə dərəcəsi də onun sırası adlanır.

İterasiya

For dövrü

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

Yuxarıdakı kod n dəfə işləyəcək. Bu kodun zaman mürəkkəbliyi O(n) dir.

While dövrü

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

Yuxarıdakı kod n dəfə işləyəcək. Bu kodun zaman mürəkkəbliyi O(n) dir.

Do while dövrü

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

Yuxarıdakı kod n dəfə işləyəcək. Bu kodun zaman mürəkkəbliyi O(n) dir.

Rekursiya

Faktorial

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

Yuxarıdakı kod n dəfə işləyəcək. Bu kodun zaman mürəkkəbliyi O(n) dir.

Fibonaççi

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

Yuxarıdakı kod n dəfə işləyəcək. Bu kodun zaman mürəkkəbliyi O(n) dir.

Axtarış

Xətti axtarış

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

Yuxarıdakı kod n dəfə işləyəcək. Bu kodun zaman mürəkkəbliyi O(n) dir.

İkili axtarış

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
}

Yuxarıdakı kod log(n) dəfə işləyəcək. Bu kodun zaman mürəkkəbliyi O(log(n)) dir.

Sıralama

Baloncuk sıralama

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
}

Yuxarıdakı kod n^2 dəfə işləyəcək. Bu kodun zaman mürəkkəbliyi O(n^2) dir.

Seçim sıralama

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
}

Yuxarıdakı kod n^2 dəfə işləyəcək. Bu kodun zaman mürəkkəbliyi O(n^2) dir.

Daxil etmə sıralama

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
}

Yuxarıdakı kod n^2 dəfə işləyəcək. Bu kodun zaman mürəkkəbliyi O(n^2) dir.

Birləşdirmə sıralama

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
}

Yuxarıdakı kod n log(n) dəfə işləyəcək. Bu kodun zaman mürəkkəbliyi O(n log(n)) dir.

Tez sıralama

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
}

Yuxarıdakı kod n log(n) dəfə işləyəcək. Bu kodun zaman mürəkkəbliyi O(n log(n)) dir.

Böyük O üçün məsləhətlər

  • Aritmetik əməliyyatlar sabitdir
  • Dəyişən təyinatı sabitdir
  • Bir massiv (indekslə) və ya obyektə (açarla) elementlərinə giriş sabitdir
  • Bir dövrədə mürəkkəblik dövrün uzunluğu ilə dövrün içərisində baş verən hər hansı bir şeyin mürəkkəbliyinin hasilinə bərabərdir

Resurslar

Twitterdə müzakirə edin

PAYLAŞ