Yayınlandı

JavaScript'te Büyük O Notasyonu

Yazarlar

Büyük O Notasyonu

Büyük O Notasyonu, toplu olarak Bachmann-Landau notasyonu veya asimptotik notasyon olarak adlandırılır, bir algoritmanın performansını tanımlamanın bir yoludur. Bir algoritmanın en kötü durum senaryosunu tanımlamak için kullanılır. Farklı algoritmaların performansını karşılaştırmak için kullanılır. Bir algoritmanın uygulanmasını giriş boyutu açısından tanımlar.

Büyük O notasyonu, fonksiyonları büyüme oranlarına göre karakterize eder: Aynı büyüme oranına sahip görevler aynı sırada kabul edilir. Bir fonksiyonun, argüman belirli bir değere veya sonsuza doğru giderken sınırlayıcı davranışını tanımlayan matematiksel bir gösterimdir. Algoritmaları, çalışma zamanları veya alan gereksinimlerinin giriş boyutu büyüdükçe nasıl büyüdüğüne göre sınıflandırmak için kullanılır. O harfi kullanılır çünkü bir fonksiyonun büyüme oranı aynı zamanda mertebesi olarak da adlandırılır.

İterasyon

For Döngüsü

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

Yukarıdaki kod n kez çalışacaktır. Bu kodun zaman karmaşıklığı O(n)'dir.

While Döngüsü

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

Yukarıdaki kod n kez çalışacaktır. Bu kodun zaman karmaşıklığı O(n)'dir.

Do While Döngüsü

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

Yukarıdaki kod n kez çalışacaktır. Bu kodun zaman karmaşıklığı O(n)'dir.

Özyineleme

Faktöriyel

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

Yukarıdaki kod n kez çalışacaktır. Bu kodun zaman karmaşıklığı O(n)'dir.

Fibonacci

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

Yukarıdaki kod n kez çalışacaktır. Bu kodun zaman karmaşıklığı O(n)'dir.

Arama

Doğrusal Arama

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

Yukarıdaki kod n kez çalışacaktır. Bu kodun zaman karmaşıklığı O(n)'dir.

İkili Arama

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
}

Yukarıdaki kod log(n) kez çalışacaktır. Bu kodun zaman karmaşıklığı O(log(n))'dir.

Sıralama

Kabarcık 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
}

Yukarıdaki kod n^2 kez çalışacaktır. Bu kodun zaman karmaşıklığı 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
}

Yukarıdaki kod n^2 kez çalışacaktır. Bu kodun zaman karmaşıklığı O(n^2)'dir.

Ekleme 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
}

Yukarıdaki kod n^2 kez çalışacaktır. Bu kodun zaman karmaşıklığı O(n^2)'dir.

Birleştirme 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
}

Yukarıdaki kod n log(n) kez çalışacaktır. Bu kodun zaman karmaşıklığı O(n log(n))'dir.

Hızlı 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
}

Yukarıdaki kod n log(n) kez çalışacaktır. Bu kodun zaman karmaşıklığı O(n log(n))'dir.

Büyük O İçin İpuçları

  • Aritmetik işlemler sabittir
  • Değişken atama sabittir
  • Bir dizideki (indekse göre) veya nesnede (anahtara göre) elemanlara erişim sabittir
  • Bir döngüde karmaşıklık, döngünün uzunluğu çarpı döngünün içinde ne olursa olsun karmaşıktır.

Kaynaklar

Twitter'da tartış

PAYLAŞ