Rappels de complexité

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

Citation:

---

Est ce bien linéaire ?

---

Non pas tout à fait.

Citation:

---

pourquoi pas logarithmique ?

---

Ca l'est puisque tu donnes la formule.

Tu tombes sur des constantes parce qu'il existe au moins une courbe (et c'est là le pb) qui passe par ces points. Tu ne peux pas déduire une complexité à partir de si peu.

Question idiote : Comment a tu trouver ta formule? Normalement on écrit un algo et on calcul sa complexité. On ne décide pas de la complexité d'un algo, pour ensuite testé si ce dernier la vérifie ou pas. non?

Salut!

Citation:

---

C = f(a)

---

Que représente pour toi la fonction f ?

Citation:

---

C1 = f(100)
C2 = f(1000)
C3 = f(10000)
C4 = f(100000)

---

Comment détermines-tu C1, C2, C3 et C4?

Jean-Marc Blanc

Tout d'abord, le type de complexité d'un algorithme donne un ordre de grandeur, pas une valeur précise. Du coup, essayer d'inférer un type de complexité par observation d'un petit échantillon de résultats n'est pas très fiable.

Ensuite, il semble que tu t'intéresses à la complexité en temps d'une fonction f. Du coup, ce que l'on mesure, c'est souvent le nombre de lecture/écriture fait en mémoire ou sur disque, le nombre de comparaisons, etc. Bref, le nombre d'opérations couteuses en temps CPU ou I/O. En revanche, on ne s'intéresse pas du tout au résultat produit par la fonction en elle même.

Or, toi, tu sembles considérer que la complexité de ta fonction EST le résultat de ladite fonction :? Que cette fonction réalise 50*log(log(A+..)) ou calcule une factorielle ou que sais-je d'autre n'a pas d'importance. La question est de savoir combien d'opérations couteuses en temps sont réalisées en rapport avec à la taille de la donnée en entrée. C'est seulement ce rapport qui te donne la complexité algorithmique.