Rapidement, la complexite c'est le nombre de fois que la boucle principale de ton applis va s'executer pour faire le travail que tu lui a demande. On utilise souvent n comme symbole du nombre d'elements a traiter.
Donc pour n elements a traiter (ou un element de taille n suivant les cas)
--- complexite constante-----
O(1) = On n'apelle qu'une seule fois la fonction, le nombre d'appels a la fonction ne depend pas du nombre d'elements a traiter (ou de la taille de l'element suivant les cas)
O(x) = On apelle x fois la fonction
---complexite logarithmique---
O(log(n)) = on apelle log(n) fois la fonction (souvent le cas du divide and conquer)
---complexite lineaire---
O(n) = On apelle n fois la fonction (le plus souvent une fois par element)
---complexite polynomiale d'ordre k---
O(n^k) = On apelle n puissance k fois la fonction (tres lent, c'est souvent le genre de complexite des AI).
---complexite exponentielle (de base k)---
O(k^n) = on apelle k puissance n fois la fonction (Cassage de clef RSA, bonne chance au fait :) )
Voila vite fait les principales complexites. Bine sur on peut avoir des complexites de type O(k^n+2n^k+4) mais ca veut pas dire grand chose, la plupart du temps on se contente du plus grand facteur (sauf pinaillage et temps reel ric-rac).
[^] # Re: Avancées technologiques du prochain Kernel
Posté par Jerome Herman . En réponse à la dépêche Avancées technologiques du prochain noyau Linux. Évalué à 7.
Donc pour n elements a traiter (ou un element de taille n suivant les cas)
--- complexite constante-----
O(1) = On n'apelle qu'une seule fois la fonction, le nombre d'appels a la fonction ne depend pas du nombre d'elements a traiter (ou de la taille de l'element suivant les cas)
O(x) = On apelle x fois la fonction
---complexite logarithmique---
O(log(n)) = on apelle log(n) fois la fonction (souvent le cas du divide and conquer)
---complexite lineaire---
O(n) = On apelle n fois la fonction (le plus souvent une fois par element)
---complexite polynomiale d'ordre k---
O(n^k) = On apelle n puissance k fois la fonction (tres lent, c'est souvent le genre de complexite des AI).
---complexite exponentielle (de base k)---
O(k^n) = on apelle k puissance n fois la fonction (Cassage de clef RSA, bonne chance au fait :) )
Voila vite fait les principales complexites. Bine sur on peut avoir des complexites de type O(k^n+2n^k+4) mais ca veut pas dire grand chose, la plupart du temps on se contente du plus grand facteur (sauf pinaillage et temps reel ric-rac).
Kha