Publié le

La notation Big O en JavaScript

Auteurs

La Notation Big O

La notation Big O, également connue sous le nom de notation de Bachmann-Landau ou notation asymptotique, est un moyen de décrire les performances d'un algorithme. Elle est utilisée pour décrire le pire scénario d'un algorithme. Elle sert à comparer les performances de différents algorithmes. Elle décrit la mise en œuvre d'un algorithme en termes de taille de l'entrée.

La notation Big O caractérise les fonctions en fonction de leurs taux de croissance : les tâches ayant le même taux de croissance sont considérées comme étant du même ordre. Il s'agit d'une notation mathématique qui décrit le comportement limitatif d'une fonction lorsque l'argument tend vers une valeur particulière ou vers l'infini. Elle est utilisée pour classer les algorithmes en fonction de la manière dont leur temps d'exécution ou leurs besoins en espace augmentent à mesure que la taille de l'entrée augmente. La lettre O est utilisée car le taux de croissance d'une fonction est également appelé son ordre.

Itération

Boucle for

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

Le code ci-dessus s'exécutera n fois. La complexité temporelle de ce code est O(n).

Boucle while

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

Le code ci-dessus s'exécutera n fois. La complexité temporelle de ce code est O(n).

Boucle do while

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

Le code ci-dessus s'exécutera n fois. La complexité temporelle de ce code est O(n).

Récursion

Factorielle

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

Le code ci-dessus s'exécutera n fois. La complexité temporelle de ce code est O(n).

Fibonacci

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

Le code ci-dessus s'exécutera n fois. La complexité temporelle de ce code est O(n).

Recherche

Recherche linéaire

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

Le code ci-dessus s'exécutera n fois. La complexité temporelle de ce code est O(n).

Recherche binaire

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
}

Le code ci-dessus s'exécutera log(n) fois. La complexité temporelle de ce code est O(log(n)).

Tri

Tri à bulles

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
}

Le code ci-dessus s'exécutera n^2 fois. La complexité temporelle de ce code est O(n^2).

Tri par sélection

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
}

Le code ci-dessus s'exécutera n^2 fois. La complexité temporelle de ce code est O(n^2).

Tri par insertion

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
}

Le code ci-dessus s'exécutera n^2 fois. La complexité temporelle de ce code est O(n^2).

Tri fusion

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
}

Le code ci-dessus s'exécutera n log(n) fois. La complexité temporelle de ce code est O(n log(n)).

Tri rapide

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
}

Le code ci-dessus s'exécutera n log(n) fois. La complexité temporelle de ce code est O(n log(n)).

Conseils pour Big O

  • Les opérations arithmétiques sont constantes.
  • L'attribution de variables est constante.
  • L'accès aux éléments d'un tableau (par index) ou d'un objet (par clé) est constant.
  • Dans une boucle, la complexité est la longueur de la boucle multipliée par la complexité de ce qui se passe à l'intérieur de la boucle.

Ressources

Discuter sur Twitter

PARTAGER