Cheat Sheet de la complexité des algorithmes Big-O (Know Thy Complexities !) @ericdrowell

Salut ! Cette page web couvre les complexités Big-O spatiales et temporelles des algorithmes courants utilisés en informatique. Lors de la préparation d’entretiens techniques dans le passé, je me suis retrouvé à passer des heures à ramper sur Internet pour rassembler les complexités du meilleur, du moyen et du pire cas pour les algorithmes de recherche et de tri afin de ne pas être bloqué lorsqu’on m’interrogeait à leur sujet. Au cours des dernières années, j’ai passé des entretiens dans plusieurs start-ups de la Silicon Valley, ainsi que dans des entreprises plus importantes, comme Google, Facebook, Yahoo, LinkedIn et Uber, et chaque fois que je me préparais à un entretien, je me disais : « Pourquoi personne n’a créé une belle antisèche Big-O ? Alors, pour vous faire gagner du temps à tous, j’ai décidé d’en créer une. Enjoy ! – Eric

Vérifiez El Grapho, une bibliothèque de visualisation de données de graphes qui prend en charge des millions de nœuds et d’arêtes

Big-O Complexity Chart

Horrible Bad Fair Good Excellent

O(log n), O(1) O(n) O(n log n) O(n^2) O(2^n) O(n !) Éléments d’opérations

Opérations courantes sur la structure de données

O(1)

Θ(log(n))

Structure de données	Complexité temporelle								Complexité spatiale
	Moyenne				Mauvaise				Mauvaise
	Accès	Recherche	Insertion	Suppression	Accès	Recherche	Insertion	Délétion
Array	`Θ(1)`	`Θ(n)`	`Θ(n)`	`Θ(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Stack	`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Queueueue	`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`	Singly-Linked List	`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`	La liste doublement-Linked List	`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Liste de saut	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n log(n))`
Tableau de hachage	`N/A`	`Θ(1)`	`Θ(1)`	`Θ(1)`	`N/A`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Arbre de recherche binaire	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Arbre cartésien	.`N/A`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`N/A`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
B-Arbre	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`	Rouge-Arbre noir	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
Arbre d’affichage	`N/A`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`N/A`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
Arbre AVL	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
KD Tree	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`

Algorithmes de tri de tableaux

Tri rapide

Algorithme	Complexité en temps			Complexité en espace
	Meilleur	Moyenne	Mauvais	Pire
`Ω(n log(n))`	`Θ(n log(n))`	`O(n^2)`	`O(log(n))`	Mergesort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`
Timsort	`Ω(n)`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`
Heapsort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n log(n))`	`O(1)`
Tri à Bulles	`Ω(n)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Tri par insertion	`Ω(n)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Tri de sélection	`Ω(n^2)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Tri de l’arbre	`Ω(n log(n))`	`Θ(n log(n))`	`O(n^2)`	`O(n)`
Shell Sort	`Ω(n log(n))`	`Θ(n(log(n))^2)`	`O(n(log(n))^2)`	`O(1)`
	Tri du seau		`Ω(n+k)`	`Θ(n+k)`	`O(n^2)`	`O(n)`
Radix Sort	`Ω(nk)`	`Θ(nk)`	`O(nk)`	`O(n+k)`
Tri de comptage	`Ω(n+k)`	`Θ(n+k)`	`O(n+k)`	`O(k)`
Cubesort	`Ω(n)`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`

En savoir plus

Cracking the Coding Interview : 150 questions et solutions de programmation
Introduction aux algorithmes, 3rd Edition
Structures de données et algorithmes en Java (2e édition)
High Performance JavaScript (Build Faster Web Application Interfaces)

Get the Official Big-O Poster Cheat Sheet

Contributeurs

Eric Rowell
Quentin Pleple
Michael Abed
Nick Dizazzo
Adam Forsyth
Felix Zhu

Jay Engineer
Josh Davis
Nodir Turakulov
Jennifer Hamon
David Dorfman
Bart Massey
Ray Pereda
Si Pham
Mike Davis
mcverry
Max. Hoffmann
Bahador Saket
Damon Davison
Alvin Wan
Alan Briolat
Drew Hannay
Andrew Rasmussen
Dennis Tsang
Vinnie Magro
Adam Arold
Alejandro Ramirez
Aneel Nazareth
Rahul Chowdhury
Jonathan McElroy
steven41292
Brandon Amos
Joel Friedly
Casper Van Gheluwe
Eric Lefevre-.Ardant
Oleg
Renfred Harper
Piper Chester
Miguel Amigot
Apurva K
Matthew Daronco
Yun-Cheng Lin
Clay Tyler
Orhan Can Ozalp
Ayman Singh
David Morton
Aurelien Ooms
Sebastian Paaske Torholm
Koushik Krishnan
Drew Bailey
Robert Burke

Améliorez cette page

Modifiez ces tableaux !

Guinguette Marais Poitevin

Blog

Know Thy Complexities! (Français)