Par exemple un algo en O(n^2) qui met 3 secondes pour processer un tableau de 100 entiers mettra 9 secondes pour en processer 200.
non il metra 12 secondes.
(2*n)^2 = 4 * n^2
Pour un algo linéaire, quand on a x fois plus de données ça prend x fois plus de temps. exemple: une addition de tableaux de x elements.
Pour un algo quadratique (O(n^2)), quand on a x fois plus de données ça prend x^2 fois plus de temps. Exemple: un tris de listes "naif" (genre tris à bulle)
Pour un algo exponetiel (O(exp(n)) quand on a x fois plus de données on va se tirer une balle ;-). Exemple le voyageur de commerce ou comment trouver le plus cours chemin passant par n points.
Pour un algo en temps constant, quelque fois l'augmentation du nb de données, le temps reste le même.
Les algo en O(n*ln n) sont les tris de listes intelligents (merge sort, quick sort, ...).
[^] # Re: Avancées technologiques du prochain Kernel
Posté par Cédric Foll . En réponse à la dépêche Avancées technologiques du prochain noyau Linux. Évalué à 3.
non il metra 12 secondes.
(2*n)^2 = 4 * n^2
Pour un algo linéaire, quand on a x fois plus de données ça prend x fois plus de temps. exemple: une addition de tableaux de x elements.
Pour un algo quadratique (O(n^2)), quand on a x fois plus de données ça prend x^2 fois plus de temps. Exemple: un tris de listes "naif" (genre tris à bulle)
Pour un algo exponetiel (O(exp(n)) quand on a x fois plus de données on va se tirer une balle ;-). Exemple le voyageur de commerce ou comment trouver le plus cours chemin passant par n points.
Pour un algo en temps constant, quelque fois l'augmentation du nb de données, le temps reste le même.
Les algo en O(n*ln n) sont les tris de listes intelligents (merge sort, quick sort, ...).