Algorithme et complexité
small1
Messages postés
8
Statut
Membre
-
KX Messages postés 19031 Statut Modérateur -
KX Messages postés 19031 Statut Modérateur -
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;
}
}
A voir également:
- Algorithme et complexité
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Algorithme application pc - Télécharger - Édition & Programmation
- Algorithme euromillion excel gratuit - Forum Algorithmes / Méthodes
- Algorithme ajout rapide snapchat - Forum Snapchat
- Ajout rapide snap - Forum Snapchat
3 réponses
En 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é !
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)
En 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.
