Compréhension théorique de l'algorithmie.

Discutez d'informatique ici !
Naed
Messages: 2
Enregistré le: 04 Mar 2020, 13:18

Compréhension théorique de l'algorithmie.

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-algorithmique

Le dernier exercice demande la compréhension de la page wiki "Algorithme de tri" en particulier ceci : https://ibb.co/2PtWggY

Je 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: 1492
Enregistré le: 05 Nov 2017, 18:32

Re: Compréhension théorique de l'algorithmie.

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

Re: Compréhension théorique de l'algorithmie.

par Naed » 04 Mar 2020, 13:44

Merci !

J'ai TOUT COMPRIS ! :twisted:

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite