Algorithme et complexité

Fermé
small1 Messages postés 8 Date d'inscription jeudi 4 avril 2013 Statut Membre Dernière intervention 26 avril 2013 - 4 avril 2013 à 20:24
KX Messages postés 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 - 4 avril 2013 à 21:48
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;
}
}

3 réponses

KX Messages postés 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 3 004
4 avril 2013 à 20:36
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é !
0
jerome9359 Messages postés 693 Date d'inscription mercredi 4 février 2009 Statut Membre Dernière intervention 10 juin 2019 159
4 avril 2013 à 20:38
Je suis d'accord mais il existe des algo de tri de complexité log(2)(N)
0
KX Messages postés 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 3 004
4 avril 2013 à 20:43
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.
0
jerome9359 Messages postés 693 Date d'inscription mercredi 4 février 2009 Statut Membre Dernière intervention 10 juin 2019 159
4 avril 2013 à 20:45
Merci pour vos précieuses informations :)
0
KX Messages postés 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 3 004
4 avril 2013 à 20:45
PS. Je ne parle ici que d'algorithmes de tri en séquentiel. On pourrait aussi avoir des tris sur des ordinateurs en parallèle, mais la complexité se calculerait différemment, et je doute que ce soit le problème de small1.
0
small1 Messages postés 8 Date d'inscription jeudi 4 avril 2013 Statut Membre Dernière intervention 26 avril 2013
4 avril 2013 à 20:56
Sa complexité est de l'ordre de N cube ,mais je n'arrive pas à voir la cause
0
jerome9359 Messages postés 693 Date d'inscription mercredi 4 février 2009 Statut Membre Dernière intervention 10 juin 2019 159
4 avril 2013 à 21:00
Je suis pourtant certain qu'il s'agit d'un algo de complexité N.
0
KX Messages postés 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 3 004
4 avril 2013 à 21:09
En effet, il est de complexité O(N), comme je l'ai déjà dit tout à l'heure.

S'il était en O(N³) tu aurais alors l'un des pires algorithmes de tri que j'ai vu (en général les moins bons sont en O(N²) ce qui est déjà assez lourd...)
0
KX Messages postés 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 3 004
4 avril 2013 à 21:11
Remarque : en fait il est possible que tu ais O(N³), mais dans ce cas là, ça voudrait dire que less(a[i], a[i-1]) et/ou exch(i, i-1) est en O(N²) mais ce serait vraiment catastrophique !
0
small1 Messages postés 8 Date d'inscription jeudi 4 avril 2013 Statut Membre Dernière intervention 26 avril 2013
4 avril 2013 à 21:36
effectivement c' est le nombre d'échange qui est du O(N²)
0
KX Messages postés 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 3 004
4 avril 2013 à 21:39
Quel genre d'échange peux-tu bien faire pour être quadratique ?
Normalement un échange sur un tableau c'est en O(1) !!!
0