Bonjour,
je ne savais vraiment pas ou poster ce sujet
Bref j'ai un algorithme, d'une certaine complexité C :
C = f(a)
Théoriquement je calcule f en quelques points :
C1 = f(100)
C2 = f(1000)
C3 = f(10000)
C4 = f(100000)
Et lorsque je fais les rapports entre ces résultats, je tombe sur :
(C1 / C2) = (C2 / C3) = (C3 / C4) = 5
Est ce que je peux dire que mon algorithme est linéaire ?
Pourtant ma fonction f est quelque chose du genre : 50*log(log(A+..)) ?
Est ce bien linéaire ? pourquoi pas logarithmique ?
Ensuite, j'implémente mon algorithme, je calcule le temps d'execution et j'ai pour les memes entrées que précédemment (100,1000,10000,100000):
(T1 / T2) = (T2 / T3) = (C3 / C4) = 5
Bon j'en déduit que j'ai bien programmé mon algorithme,
Pour etre clair, ce que je souhaite faire c'est vérifier que mon implémentation concorde bien avec la complexité théorique attendu.
Dans ce cas ca semble le cas, mais si j'avais quelque chose comme :
(T1 / T2) = (T2 / T3) = (C3 / C4) = 15
Est ce que ca serait le cas également ? C'est linéaire, que je sois tombé sur la meme proportion, le meme facteur 5, est ce un coup de chance ?
Si quelqu'un pouvait m'éclairer
merci
Partager