⏱️

Notation Big O

44 cards · 🇺🇸 English → 🇫🇷 Français

Analyse de la complexité temporelle et spatiale des algorithmes et opérations courantes.

Study all 44 cards for free

Flashcards, quizzes, pixel-art games and a daily review that remembers for you.

Study this deck free

Try the first 10 cards

1 / 10

Question

Big O notation

Knew itLearning

Tap the card for the answer · swipe right if you knew it, left if not

Already have an account? Sign in

Cards

1Big O notation
Une notation mathématique qui décrit le comportement limite d'une fonction lorsque l'argument tend vers l'infini, utilisée pour classer les algorithmes selon la façon dont leur temps d'exécution ou leurs besoins en espace croissent avec la taille de l'entrée
2Letter 'O'
Ordnung (allemand pour « ordre »), qui signifie l'ordre d'approximation
3F(n) = O(g(n))
La fonction f est bornée supérieurement par g (à un facteur constant près) de façon asymptotique
4O(1) complexity
Temps constant - l'algorithme prend le même temps quelle que soit la taille de l'entrée
5O(log n) complexity
Temps logarithmique - typique des algorithmes qui divisent le problème en deux à chaque étape (par exemple, la recherche dichotomique)
6O(n) complexity
Temps linéaire - le temps d'exécution de l'algorithme croît linéairement avec la taille de l'entrée
7O(n log n) complexity
Temps linéarithmique ou quasi-linéaire - typique des algorithmes de tri par comparaison efficaces comme le tri fusion et le tri par tas
8O(2ⁿ) complexity
Temps exponentiel - le temps d'exécution double à chaque élément supplémentaire de l'entrée
9Little-o notation
Une notation où f(n) = o(g(n)) signifie que f croît beaucoup plus lentement que g de façon asymptotique
10Big Omega (Ω) notation
Une notation qui fournit une borne inférieure sur le taux de croissance d'une fonction (f est bornée inférieurement par g)
11Big Theta (Θ) notation
Une notation signifiant que f est bornée par g à la fois par au-dessus et par en-dessous (borne serrée) - f et g ont le même ordre de croissance
12F(n) ~ g(n)
Équivalence asymptotique - f est égale à g de façon asymptotique (le rapport f/g tend vers 1)
13Complexity of finding an item in a sorted array with binary search
O(log n)
14Complexity of finding an item in an unsorted list with linear search
O(n)
15Best possible time complexity for comparison-based sorting
O(n log n) dans le cas moyen
16Time complexity of quicksort in the average case
O(n log n)
17Worst-case time complexity of quicksort
O(n²)
18Time complexity of merge sort
O(n log n) dans tous les cas (meilleur, moyen et pire)
19Time complexity of bubble sort
O(n²) dans les pires et moyens cas, O(n) dans le meilleur cas (déjà trié)
20Time complexity of insertion sort
O(n²) dans les pires et moyens cas, O(n) dans le meilleur cas
21Space complexity of an algorithm
La quantité d'espace mémoire supplémentaire requise par l'algorithme en fonction de la taille de l'entrée
22'in-place'
Un algorithme qui ne nécessite qu'un espace supplémentaire de O(1) ou O(log n) au-delà de l'entrée
23Amortized time complexity
Le temps moyen par opération sur une séquence d'opérations dans le pire cas
24Inverse Ackermann function's complexity
O(α(n)), qui croît extrêmement lentement - pratiquement constante en pratique (utilisée dans les opérations sur les ensembles disjoints)
25Polylogarithmic time
O((log n)^k) pour une certaine constante k - plus lent que le logarithmique mais plus rapide que tout polynôme
26Superpolynomial function
Une fonction qui croît plus vite que n^c pour toute constante c
27Subexponential function
Une fonction qui croît plus lentement que c^n pour toute constante c > 1
28Can you ignore constant factors in Big O notation?
Oui, les constantes sont omises : O(5n) = O(n), O(3n²) = O(n²)
29Can you drop lower-order terms in Big O notation?
Oui : O(n² + n) = O(n²), O(n³ + n² + n) = O(n³)
30Is Big O notation an equality or an inequality?
C'est en fait une inégalité (borne supérieure) malgré l'utilisation du symbole =, représentant l'appartenance (« est élément de ») à un ensemble