Algorithme et complexité
Bonsoir à tous je n'arrive pas à Analyser le temps d'exécution asymptotique de l'algorithme suivant.
Précisions: less effectue une comparaison et exch effectue l'échange en gros cet algorithme effectue le tri d'un tableau. Merci
for (int i = 1; i < N; i++) {
if (less(a[i], a[i-1])) {
exch(i, i-1);
i = 0;
}
}
Précisions: less effectue une comparaison et exch effectue l'échange en gros cet algorithme effectue le tri d'un tableau. Merci
for (int i = 1; i < N; i++) {
if (less(a[i], a[i-1])) {
exch(i, i-1);
i = 0;
}
}
3 réponses
-
ModérateurEn gros : tu as une boucle qui dépend de N, donc ta complexité est O(N).
PS. Il est impossible que ton algorithme de tri fonctionne comme ça, ou alors tu aurais le meilleur algorithme de tri qui n'ai jamais été développé ! -
Je suis d'accord mais il existe des algo de tri de complexité log(2)(N)
-
ModérateurEn O(log2(N)) ce sont des algorithmes de maintien du tri. C'est à dire qu'on ajoute une seule valeur à un ensemble déjà trié. Ce qui explique pourquoi les meilleurs algorithmes de tri (sous-entendu sur des ensembles quelconques au départ) sont en O(N.log2(N)) puisqu'il faut ajouter N valeurs sur un ensemble vide au départ qui se maintient en O(log2(N)) à chaque ajout d'un élément.
-
-
-
-
Sa complexité est de l'ordre de N cube ,mais je n'arrive pas à voir la cause
