Salut,

J'ai un projet d'expérimentation en complexité algorithmique à réaliser, et je me retrouve à tracer des graphiques avec gnuplot pour illustrer le temps de calcul de différents algorithmes. J'ai donc un fichier data qui mappe une taille d'entrée à un temps d'exécution en ms, que je plot avec gnuplot sans problèmes.

Par contre, j'aimerais pouvoir tracer sur le même graphique, les courbes de référence liées à leur complexité théorique ; par exemple, j'aimerais tracer la courbe f(x) = x*x pour la comparer avec la courbe de temps réel si je sais que mon algorithme a une complexité moyenne théorique quadratique. Je sais bien qu'il y aura un écart et que les deux ne sont pas comparables en soi puisque l'une est quantifiée en ms et l'autre en opérations fondamentales, mais c'est justement un des points vers lesquels je dois aller pour l'exercice.

Le problème est que, du coup, je ne sais pas comment la plotter correctement dans gnuplot. Puisque je plot mes données expérimentales, je me retrouve avec des ms en ordonnés pour des "tailles d'instance" en abscisses, et si je fais un "f(x) = x*x; plot f(x) <...>" ça n'a aucun sens puisqu'il map alors des tailles arbitraires au carré à des ms.
La solution serait de savoir combien d'instructions par seconde mon processeur peut réaliser, et entrer les données moi-même pour avoir une allure à peu près signifiante par rapport aux unités, mais ça me semble pas possible puisque ce nombre est variable sur un même processeur et pas vraiment indicatif.

Du coup, quelqu'un a une idée de comment je peux plotter correctement une courbe tirée d'une expérimentation (ms/nombre d'entrées) et une fonction de référence (opérations/nombre d'entrées) dans le même repère ? J'ai beaucoup de mal à voir comment donner un sens à tout ça, mais c'est manifestement ce qu'on nous demande...

Merci.

Si ton algo est en O(x^2) ce que ca veut dire c'est que (apres un certain ordre), le temps de calcul est inferieur a c x^2. Donc pour tracer O(x^2) tu peux prendre n'importe c que tu veux. Ca te laisse en gros 3 choix:

1/ tu prends un c au pif jusqu'a ce que la courbe qie une belle gueule.

2/ tu prends le c qui correspod a un de tes points, en general prendre le dernier c'est pas mal

3/ tu fais une regressiono quadratique et tu prends ce coeff la.

En general je prends option 2.

Une autre facon de faire est de ne pas plotter le temps de calcul, mais de plotter la constante en plottant tempsdecalcul/x^2. Ainsi toute borne sup dela courbe est un c qui a l'air de marcher. Et ca permet de faire la difference entre O(x^2), Theta(x^2), Omega(x^2), o(x^2) et omega(x^2).

Merci beaucoup Godrik, super réponse !
Du coup je suis parti sur ta seconde idée ; je plot ma courbe de données normalement, et à côté une fonction f(x) = c * <complexité théorique de l'algo sur x>, avec c = <dernier point y> / <complexité théorique de l'algo pour ce dernier point>, du style f(x) = (50000/1000**2) * x**2 pour un algo quadratique dont l'expérimentation montre un temps de 50000 pour 1000 entrées, par exemple.
Je sais pas si c'est exactement ce que tu me conseillais, en tout cas les résultats semblent plausibles ; sur des petits inputs, toutes les implémentations présentent un écart (supérieur) relativement important par rapport à la courbe théorique ainsi tracée, écart qui diminue plus la taille des entrées augmente.

Moralement c'est ca que je voulais dire. Ca montre toujours un peu le probleme avec le concept de complexite. Tu ne sais jamais vraiment quel est la constante. Aussi O etant une borne sup du temps de calcul, tu ne peux pas dire grand chose de tres intelligent. L'idee ici est juste de confirme l'intuition.