Algorithme et complexité
small1
Messages postés
8
Date d'inscription
Statut
Membre
Dernière intervention
-
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é
- Algorithme euromillion excel gratuit - Télécharger - Loisirs créatifs
- Algorithme ajout rapide snapchat - Forum Snapchat
- Ce mot de passe ne répond pas aux critères de longueur, de complexité, de date ou d'historique de la stratégie de mot de passe de votre entreprise. - Forum Windows
- ALgorithme dans Algobox - Forum Algorithmes / Méthodes
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
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é !
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.
