Compréhension théorique de l'algorithmie.
Discutez d'informatique ici !
-
Naed
- Messages: 2
- Enregistré le: 04 Mar 2020, 13:18
-
par Naed » 04 Mar 2020, 13:31
Bonjour,
Je suis en pleine initiation à l'algorithmie.
J'ai fais tous les exercices Algorithmiques du site Grafikart
https://www.grafikart.fr/formations/apprendre-algorithmiqueLe dernier exercice demande la compréhension de la page wiki
"Algorithme de tri" en particulier ceci :
https://ibb.co/2PtWggYJe ne comprend pas le
n log n je sais qu'il s'agit de logarithmie mais j'aimerai qu'on accompagne mon Cerveau pour comprendre les 10 puissances et leurs lien avec la formule.
Gracias la populas !
Modifié en dernier par
Naed le 04 Mar 2020, 13:43, modifié 2 fois.
-
LB2
- Habitué(e)
- Messages: 1504
- Enregistré le: 05 Nov 2017, 18:32
-
par LB2 » 04 Mar 2020, 13:39
Bonjour,
il s'agit de comprendre la notion de complexité d'un algorithme.
Grossièrement, c'est le temps de calcul que prend un algorithme pour une entrée de taille n.
On utilise une notation mathématique (de Landau) appelée "grand O", notée O(...) pour désigner cette complexité. Dans un premier temps tu peux te permettre de considérer que O(...) signifie ("d'ordre de grandeur ...")
Par exemple, un algorithme de complexité O(n) signifie que lorsqu'on multiplie la taille de l'entrée par 2 , le temps de calcul nécessaire est également multiplié par 2.
Un algorithme de complexité O(n^2) : on multiplie la taille de l'entrée par 2, le temps de calcul est multiplié par 4.
O(nlogn) se situe entre ces deux valeurs : on a l'encadrement mathématique n <= nlog(n) <= n^2.
C'est nettement plus rapide que n^2, mais un peu plus lent que n.
Application numérique pour n grand, n=10^10 (nombre à dix chiffres)
n = 10^10
nlog(n) = 10*10^10 = 10^11
n^2 = 10^20
Maintenant, comprendre pourquoi tel algorithme de tri est de telle complexité, il faut une démonstration, tu peux te contenter de l'admettre dans un premier temps. Mais il faut comprendre qu'il y a la famille des tris "naïfs" en O(n^2) et les tris "moins naïfs" en O(nlog(n)), plus rapides.
-
Naed
- Messages: 2
- Enregistré le: 04 Mar 2020, 13:18
-
par Naed » 04 Mar 2020, 13:44
Merci !
J'ai TOUT COMPRIS !
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 4 invités