Publikuar më

Numri më i madh në JavaScript në O

Autorët

Notimi i Madh O, Notueshmëria e Bachmann-Landau ose Notueshmëria Asimptotike

Notimi i Madh O, i quajtur kolektivisht Notueshmëria e Bachmann-Landau ose Notueshmëria Asimptotike, është një mënyrë për të përshkruar performancën e një algoritmi. Ai përdoret për të përshkruar skenarin më të keq të një algoritmi. Ai përdoret për të krahasuar performancën e algoritmeve të ndryshme. Ai përshkruan zbatimin e një algoritmi në terma të madhësisë së hyrjes.

Notimi i Madh O karakterizon funksionet sipas shkallëve të tyre të rritjes: detyrat me të njëjtën shkallë të rritjes konsiderohen të jenë të të njëjtit rend. Është një notueshmëri matematikore që përshkruan sjelljen kufizuese të një funksioni kur argumenti tenon të afrohet një vlere të veçantë ose infiniti. Ai përdoret për të klasifikuar algoritmet sipas asaj se si koha e tyre e ekzekutimit ose kërkesat e hapësirës rriten kur madhësia e hyrjes rritet. Shkronja O përdoret sepse shkalla e rritjes së një funksioni quhet gjithashtu rendi i tij.

Iterimi

Lak i For

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

Kodi i mësipërm do të ekzekutohet n herë. Kompleksia e kohës së këtij kodi është O(n).

Lak i While

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

Kodi i mësipërm do të ekzekutohet n herë. Kompleksia e kohës së këtij kodi është O(n).

Lak i Do While

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

Kodi i mësipërm do të ekzekutohet n herë. Kompleksia e kohës së këtij kodi është O(n).

Rekursion

Faktoriel

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

Kodi i mësipërm do të ekzekutohet n herë. Kompleksia e kohës së këtij kodi është O(n).

Fibonacci

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

Kodi i mësipërm do të ekzekutohet n herë. Kompleksia e kohës së këtij kodi është O(n).

Kërkimi

Kërkimi Linear

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

Kodi i mësipërm do të ekzekutohet n herë. Kompleksia e kohës së këtij kodi është O(n).

Kërkimi Binare

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
}

Kodi i mësipërm do të ekzekutohet log(n) herë. Kompleksia e kohës së këtij kodi është O(log(n)).

Renditja

Renditja me Flluska

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
}

Kodi i mësipërm do të ekzekutohet n^2 herë. Kompleksia e kohës së këtij kodi është O(n^2).

Renditja me Selektim

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
}

Kodi i mësipërm do të ekzekutohet n^2 herë. Kompleksia e kohës së këtij kodi është O(n^2).

Renditja me Futje

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
}

Kodi i mësipërm do të ekzekutohet n^2 herë. Kompleksia e kohës së këtij kodi është O(n^2).

Renditja me Bashkim

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
}

Kodi i mësipërm do të ekzekutohet n log(n) herë. Kompleksia e kohës së këtij kodi është O(n log(n)).

Renditja e Shpejtë

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
}

Kodi i mësipërm do të ekzekutohet n log(n) herë. Kompleksia e kohës së këtij kodi është O(n log(n)).

Këshilla për Big O

  • Operacionet aritmetike janë konstante
  • Asignimet e ndryshoreve janë konstante
  • Qasja në elementët e një array (me indeks) ose objektit (me çelës) është konstante
  • Në një lak, kompleksia është gjatësia e lakit shumëzuar me kompleksitetin e asaj që ndodh brenda lakit

Burime

Diskuto në Twitter

NDAJ