Je ne mémorise jamais ces trucs, alors comme pour la Nième fois je tombe sur ces notions dans un bon bouquin (The Practice Of Programming de Kernighan et Pike) autant en faire une petite note.
| Notation | Nom | Exemple |
|---|---|---|
| O(1) | constant | array index |
| O(log n) | logarithmic | binary search |
| O(n) | linear | string comparison |
| O(n log n) | n log n | quicksort |
| O(n**2) | quadratic | simple sorting methods |
| O(n**3) | cubic | matrix multiplication |
| O(2**n) | exponential | set partitioning |
D'accord? pas d'accord? suggestions? faute d'orthographe?