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
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
A voir également:
- Algorithme et complexité
- Ppcm algorithme - Forum Programmation
- Pgcd algorithme - Forum Programmation
- Ecrire un algorithme qui permet de resoudre ax²+bx+c=0 - Forum Algorithmes / Méthodes
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Algorithme excel - Forum VB / VBA
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
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é !
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é !
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
4 avril 2013 à 20:38
Je suis d'accord mais il existe des algo de tri de complexité log(2)(N)
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
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.
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
4 avril 2013 à 20:45
Merci pour vos précieuses informations :)
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
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.
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
4 avril 2013 à 20:56
Sa complexité est de l'ordre de N cube ,mais je n'arrive pas à voir la cause
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
4 avril 2013 à 21:00
Je suis pourtant certain qu'il s'agit d'un algo de complexité N.
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
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...)
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...)
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
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 !
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
4 avril 2013 à 21:36
effectivement c' est le nombre d'échange qui est du O(N²)
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
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) !!!
Normalement un échange sur un tableau c'est en O(1) !!!