Comparing algorithms and ADTs in algorithms · Comparaison des algorithmes et des types abstraits de données (ADT) en algorithmique
| English | Français |
|---|---|
| Big-O/bɪɡ əʊ/ | Big-O |
| time complexity/taɪm kəmˈpleksɪti/ | complexité temporelle |
| space complexity/speɪs kəmˈpleksɪti/ | complexité spatiale |
| depth-first/depθ fɜːst/ | profondeur d'abord |
| breadth-first/bredθ fɜːst/ | largeur d'abord |
| binary tree/ˈbaɪnəri triː/ | arbre binaire |
The algorithm that would outlive the universe
- A salesman must visit 25 cities and return home by the shortest route. Try every order and there are about $10^{23}$ of them. A machine checking a billion a second would take three million years.
- Add one more city and the work multiplies by 25. That is not a computer that needs to be faster; it is an approach that can never work, at any speed, on any hardware.
- Knowing that before you write the program is what complexity analysis is for. It is the difference between choosing an algorithm and discovering, months later, that yours does not scale.
- This lesson is Big-O 大O表示法 for time and space, and how ADTs shape the algorithms built on them.
L'algorithme qui survivrait à l'univers
- Un commercial doit visiter 25 villes et rentrer chez lui par l'itinéraire le plus court. Essayez chaque ordre et il y en a environ $10^{23}$. Une machine vérifiant un milliard par seconde mettrait trois millions d'années.
- Ajoutez une ville de plus et le travail multiplie par 25. Ce n'est pas un ordinateur qui a besoin d'être plus rapide ; c'est une approche qui ne peut jamais fonctionner, à aucune vitesse, sur aucun matériel.
- Savoir cela avant d'écrire le programme, c'est ce dont sert l'analyse de complexité. C'est la différence entre choisir un algorithme et découvrir, des mois plus tard, que le vôtre ne met pas à l'échelle.
- Cette leçon porte sur la notation Big-O 大O表示法 pour le temps et l'espace, et sur la façon dont les ADT façonnent les algorithmes construits dessus.
Time complexity
- Time complexity 时间复杂度 describes how the running time grows with the input size $n$. It is written in Big-O notation, which keeps only the dominant term and drops constants.
- $O(1)$ constant, the time does not depend on $n$ at all. $O(\log n)$ logarithmic, as in binary search. $O(n)$ linear, as in linear search. $O(n \log n)$, the good sorts. $O(n^2)$ quadratic, as in bubble and insertion sort.
- The reason constants are dropped: they are swamped. An $O(n^2)$ algorithm might beat an $O(n \log n)$ one for $n = 10$, but at $n = 10{,}000$ nothing about the constants can save it.
The curves cross once, and after that the order decides everything
Complexité temporelle
- La complexité temporelle 时间复杂度 décrit comment le temps d'exécution augmente avec la taille de l'entrée $n$. Elle s'écrit en notation Big-O, qui ne conserve que le terme dominant et élimine les constantes.
- $O(1)$ constant, le temps ne dépend pas du tout de $n$. $O(\log n)$ logarithmique, comme dans la recherche dichotomique. $O(n)$ linéaire, comme dans la recherche linéaire. $O(n \log n)$, les bons triages. $O(n^2)$ quadratique, comme dans le tri à bulles et le tri par insertion.
- La raison pour laquelle on élimine les constantes : elles sont masquées. Un algorithme $O(n^2)$ peut battre un $O(n \log n)$ pour $n = 10$, mais à $n = 10{,}000$, rien au sujet des constantes ne peut le sauver.
Les courbes se croisent une fois, et après cela, l'ordre décide de tout
How running time grows with n · La croissance du temps d'exécution avec n
Slide n upward and compare the curves: O(1) and O(log n) stay almost flat, O(n) rises steadily, O(n²) explodes. This is why Big-O — not a stopwatch — is how we compare algorithms on large inputs. · Faites glisser n vers le haut et comparez les courbes : O(1) et O(log n) restent presque plats, O(n) monte régulièrement, O(n²) explose. C'est pourquoi le Big-O — et non un chronomètre — est la manière dont nous comparons les algorithmes sur de grandes entrées.
Which Big-O describes binary search? · Quel Big-O décrit la recherche binaire ?
Halving the range each step is logarithmic — O(log n). · Réduire l'intervalle de moitié à chaque étape est logarithmique — O(log n).
Which Big-O describes bubble sort in the worst case? · Quel Big-O décrit le tri à bulles au pire cas ?
Two nested loops over n elements give O(n²). · Deux boucles imbriquées sur n éléments donnent O(n²).
Match each algorithm to its time complexity. · Reliez chaque algorithme à sa complexité temporelle.
Linear search is O(n), binary search O(log n), bubble sort O(n²). · Recherche linéaire O(n), recherche binaire O(log n), tri à bulles O(n²).
Worked example: what doubling the input does
- An algorithm takes 4 seconds on 1,000 items. Estimate its time on 2,000 items if it is $O(n)$, then if it is $O(n^2)$.
- $O(n)$: doubling $n$ doubles the time, so about 8 seconds.
- $O(n^2)$: doubling $n$ quadruples the time, so about 16 seconds. At 10,000 items it would be 100 times the original, about 400 seconds.
- $O(\log n)$ would add only a single step, and $O(1)$ would not change at all. Reason from the order, not from a formula.
Exemple résolu : ce que fait doubler l'entrée
- Un algorithme prend 4 secondes pour traiter 1,000 éléments. Estimez son temps d'exécution sur 2,000 éléments s'il est de complexité $O(n)$, puis s'il est de complexité $O(n^2)$.
- $O(n)$ : doubler $n$ double le temps, donc environ 8 secondes.
- $O(n^2)$ : doubler $n$ quadruple le temps, soit environ 16 secondes. Avec 10,000 éléments, cela serait 100 fois l'original, environ 400 secondes.
- $O(\log n)$ n'ajouterait qu'une seule étape, et $O(1)$ ne changerait pas du tout. Raisonnez à partir de l'ordre, pas d'une formule.
An O(n squared) algorithm takes 4 seconds on 1,000 items. Roughly how many seconds will it take on 2,000? · Un algorithme de complexité O(n²) prend 4 secondes pour traiter 1,000 éléments. Combien de secondes prendra-t-il approximativement pour 2,000 ?
Doubling n quadruples an O(n squared) time. The same doubling would take an O(n) algorithm from 4 seconds to 8. · Doubler n quadruple le temps d'un algorithme O(n squared). Le même double passerait un algorithme O(n) de 4 secondes à 8.
Space complexity
- Space complexity 空间复杂度 is the extra memory an algorithm needs, beyond the input itself.
- Bubble and insertion sort use $O(1)$ extra memory: they work in place, needing only a couple of variables. Merge sort uses $O(n)$, since it builds a second array.
- Recursion uses stack memory proportional to its depth, because every unfinished call keeps its own frame.
- There is often a time and memory trade-off: storing results to avoid recomputing them, as memoisation does, buys speed with space.
Complexité spatiale
- La complexité spatiale 空间复杂度 est la mémoire supplémentaire qu'un algorithme nécessite, au-delà de l'entrée elle-même.
- Les tris à bulles et par insertion utilisent $O(1)$ mémoire supplémentaire : ils fonctionnent in-place, nécessitant seulement quelques variables. Merge sort utilise $O(n)$, car il construit un second tableau.
- La récursion utilise de la mémoire de pile proportionnelle à sa profondeur, car chaque appel non terminé garde sa propre frame.
- Il existe souvent un compromis temps/mémoire : stocker des résultats pour éviter de les recalculer, comme le fait la mémoïsation, achète de la vitesse avec de l'espace.
What else decides the choice
- Big-O is about growth, not absolute speed. For a small $n$, a simple $O(n^2)$ algorithm can beat a complicated $O(n \log n)$ one, and it is easier to write correctly.
- Stability matters when a list is already ordered by another field. Simplicity matters because a simple algorithm has fewer places to hide a bug.
- The honest answer to "which algorithm" often names the order and the conditions: this one, because $n$ is large and the data arrives unsorted.
Ce qui détermine aussi le choix
- Big-O concerne la croissance, pas la vitesse absolue. Pour une petite $n$, un algorithme simple $O(n^2)$ peut battre un complexe $O(n \log n)$, et il est plus facile à écrire correctement.
- La stabilité compte lorsqu'une liste est déjà ordonnée selon un autre champ. La simplicité compte car un algorithme simple a moins d'endroits où cacher un bug.
- La réponse honnête à « quel algorithme » nomme souvent l'ordre et les conditions : celui-ci, parce que $n$ est grand et que les données arrivent non triées.
An "in place" sort: · Un tri "in place" :
In-place algorithms (like bubble and insertion sort) sort within the original array, using constant extra space. · Les algorithmes in-place (comme le tri à bulles et par insertion) trient dans le tableau original, utilisant un espace constant supplémentaire.
Why is bubble sort's space complexity O(1) even though it sorts an array of n items? · Pourquoi la complexité spatiale du tri à bulles est-elle O(1) alors qu'il trie un tableau de n éléments ?
It sorts in place. Merge sort is O(n) because it builds a second array, and recursion costs memory proportional to its depth. · Il trie in-place. Le tri fusion est O(n) car il construit un second tableau, et la récursivité coûte une mémoire proportionnelle à sa profondeur.
ADTs inside algorithms
- The abstract data types from topic 10 are the machinery algorithms are built from, and choosing one shapes the algorithm.
- A stack gives depth-first 深度优先 search: push the neighbours, take the most recent, and the search plunges down one path before backing up. Recursion uses the call stack for exactly this.
- A queue gives breadth-first 广度优先 search: enqueue the neighbours, take the oldest, and the search spreads outward in rings, which is what finds the shortest path in an unweighted graph.
- A binary tree 二叉树 keeps values in order so that a search discards half the remaining nodes at each step, giving binary search's $O(\log n)$ over a structure that can also grow.
ADT dans les algorithmes
- Les types de données abstraits du chapitre 10 sont le mécanisme dont les algorithmes sont construits, et en choisir un façonne l'algorithme.
- Une pile donne une recherche depth-first 深度优先 : empiler les voisins, prendre le plus récent, et la recherche plonge vers le bas d'un chemin avant de revenir en arrière. La récursion utilise la pile d'appels exactement pour cela.
- Une file donne une recherche breadth-first 广度优先 : enfiler les voisins, prendre le plus ancien, et la recherche s'étend vers l'extérieur en anneaux, ce qui trouve le chemin le plus court dans un graphe non pondéré.
- Un arbre binaire 二叉树 garde les valeurs en ordre afin qu'une recherche élimine la moitié des nœuds restants à chaque étape, donnant la recherche dichotomique $O(\log n)$ sur une structure qui peut aussi croître.
Which statements about Big-O are correct? Select all · tout that apply. · Quelles affirmations sur le Big-O sont correctes ? Sélectionnez toutes les options qui s'appliquent.
Big-O says nothing about seconds; it is about growth. That is why the crossover with a simpler algorithm exists at small sizes. · Big-O ne dit rien sur les secondes ; il porte sur la croissance. C'est pourquoi le point de croisement avec un algorithme plus simple existe aux petites tailles.
Worked example: the same graph, two searches
- A maze is explored from one entrance. Contrast using a stack with using a queue.
- With a stack, the most recently found path is explored next, so the search goes deep down one route until it dead-ends, then backtracks. It uses memory proportional to the depth of the path.
- With a queue, the oldest found path is explored next, so the search examines everything one step away, then everything two steps away. It finds the shortest route first, but holds every position at the current distance in memory.
- Name the ADT, name the resulting order of exploration, and name the consequence.
Exemple résolu : le même graphe, deux recherches
- Un labyrinthe est exploré depuis une entrée. Contrastez l'utilisation d'une pile avec celle d'une file.
- Avec une pile, le chemin trouvé le plus récemment est exploré en dernier, donc la recherche va profondément le long d'une route jusqu'à ce qu'elle bute, puis revient en arrière. Elle utilise une mémoire proportionnelle à la profondeur du chemin.
- Avec une file, le chemin trouvé le plus ancien est exploré en dernier, donc la recherche examine tout ce qui est à un pas, puis tout ce qui est à deux pas. Elle trouve la route la plus courte en premier, mais garde toutes les positions à la distance actuelle en mémoire.
- Nommez l'ADT, nommez l'ordre d'exploration résultant, et nommez la conséquence.
A stack (LIFO) naturally drives a depth-first traversal, while a queue (FIFO) drives a breadth-first traversal. · Une pile (LIFO) conduit naturellement à une traversal en profondeur, tandis qu'une file (FIFO) conduit à une traversal en largeur.
The ADT you choose decides the search order — stack goes deep first, queue explores level by level. · L'ADT que vous choisissez dicte l'ordre de recherche : la pile va profondément, la file explore niveau par niveau.
Match each ADT to the search it produces and its consequence. · Reliez chaque ADT à la recherche qu'il produit et à sa conséquence.
Most recent first, or oldest first. That single choice decides whether the search goes deep or wide. · Plus récent en premier, ou plus ancien en premier. Ce seul choix dicte si la recherche est profonde ou large.
Marks that slip away
- Big-O describes growth with input size, not seconds. "It is fast" is not a complexity answer.
- Doubling the input doubles an $O(n)$ time and quadruples an $O(n^2)$ one. Reason from the order.
- Space complexity is the extra memory, which is why an in-place sort is $O(1)$ even though the array is size $n$.
- Stack gives depth-first, queue gives breadth-first. Getting that pair the right way round is the whole of several questions.
Pièges qui font perdre des points
- Big-O décrit la croissance avec la taille de l'entrée, pas les secondes. « C'est rapide » n'est pas une réponse de complexité.
- Doubler l'entrée double un temps $O(n)$ et quadruple un $O(n^2)$. Raisonnez à partir de l'ordre.
- La complexité spatiale est la mémoire supplémentaire, c'est pourquoi un tri in-place est $O(1)$ même si le tableau a une taille $n$.
- La pile donne depth-first, la file donne breadth-first. Inverser cette paire est l'essentiel de plusieurs questions.
You've got it
- time complexity in Big-O describes growth with $n$: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$; constants are dropped because at scale the order decides
- doubling $n$ doubles $O(n)$ and quadruples $O(n^2)$; the crossover with a "worse" algorithm only exists for small $n$
- space complexity is the extra memory: in place sorts are $O(1)$, merge sort is $O(n)$, and recursion costs stack depth
- a stack gives depth-first search, a queue gives breadth-first, and a binary tree halves the remaining nodes at each step
Vous avez compris
- la complexité temporelle en Big-O décrit la croissance par rapport à $n$ : $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$ ; les constantes sont ignorées car à grande échelle, l'ordre décide
- doubler $n$ double $O(n)$ et quadruple $O(n^2)$ ; le point de croisement avec un algorithme « pire » n'existe que pour de petites valeurs de $n$
- la complexité spatiale est la mémoire supplémentaire : les tris in place sont $O(1)$, le tri fusion est $O(n)$, et la récursion coûte en profondeur de pile
- une pile donne une recherche en profondeur, une file donne une recherche en largeur, et un arbre binaire divise par deux les nœuds restants à chaque étape