Algorithme et complexité
small1
Messages postés
8
Date d'inscription
Statut
Membre
Dernière intervention
-
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
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
- Logiciel algorithme gratuit - 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.
Sa complexité est de l'ordre de N cube ,mais je n'arrive pas à voir la cause
