Discussion :

[Artiphys]

Bonjour,

je travail sur un rapport concernant les algorithmes des tris. On me demande de choisir trois algorithmes sur les quels travailler, j'ai choisis tri par comptage, tri à bulles, tri par tas.

Il faut d'abord modélisé leur complexité de façon mathématique et après par régression linéaire trouver les constantes associées. Pas de soucis pour ça.

Mais ensuite on me demande ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Evaluez la valeur du c dans de la complexité O(n^c) pour les deux tris de complexité O(n^2) et O(n).

J'ai beau chercher sur le net, je ne trouve rien ! Quelqu'un peut-il m'en dire plus sur cette évaluation empirique ?

Je vous remercie !

[davly]

La question n'est pas assez précise, mais vu le titre que tu donne au poste..

Déjà dans les tris tu ne pourra jamais avoir une complexité meilleur que
O(n ln(n))
exception près du tri spaghetti qui n'est pas informatique.

Revenons à ta question, par exemple un tri bulle à une complexité moyenne de
O(n ln(n))
Par contre si tu met en entrée un tableau ranger par ordre décroissant, la compléxité de ce cas la donne O(n²).
C'est le coté empirique.. (le pire des cas).

Je sais pas si ça répond à ta question.

David.

[Franck Dernoncourt]

J'avoue que je vois pas trop ce que désigne le terme "évaluation empirique de la complexité" : personnellement je l'interpréterai comme une incitation à comparer les performances d'une implémentation en fonction de différents inputs.

exception près du tri spaghetti qui n'est pas informatique.

En O(n) tu as aussi le bead-sort, en théorie
http://www.scribd.com/doc/55808256/2...ting-Algorithm

[souviron34]

bah c'est assez facile..

Comme le dit Franck, tu prends des entrées de tailles croissantes, et tu compares les temps de calcul (ou tu les traces)...

O(N) -> Temps/N = constante

O(N2) -> Temps / N2 = constante

etc..


Par contre, pour que le temps mesuré soit significatf, il faut faire des boucles 'appel des tris (par exemple 10000 ou 100000 fois) et prendre la moyenne du temps (pour enlever la partie "chargement" du programme), et si possible être le seul à tourner..

[Franck Dernoncourt]

Pour compléter la réponse de souviron34 et expliciter davantage la mienne, par différents inputs j'entendais considérer des entrées de taille différente (croissante en effet c'est le plus classique) ainsi que des entrées différentes mais de même taille (car certains algorithmes sont sensibles par exemple à l'ordre des items d'un tableau, typiquement les algorithmes de tri) : néanmoins ce deuxième point est beaucoup moins important que le premier, voire inutile, car la plupart du temps dans boucles 'appel des tris' tu génèras des entrées aléatoires. Cela dépend de ce que tu veux évaluer précisément