Je travaille sur des complexités logarithmiques et j'essaie de prouver que le nombre de pas nécessaires pour un routage glouton dans une distribution 2-harmonique dans un graphe de type anneau de n noeuds vaut
O((n/logn)*log(log(n))
Pour trouver la complexité je dispose de deux lemmes démontrés.EN utilisant le premier lemme ainsi que le second lemme qui nous dit que:
Soit g(x) une fonction monotone non croissante deR+ dans R+ .Une particule partant de 0 et se déplacant selon une ligne discrète de 0 à n et pour laquelle la position change dans des intervalles de temps discrets. Si la particule est en s, elle se déplace à la position s+X où X est une variable aléatoire de valeur comprise entre 1 et n-s tel que
Si T est une variable aléatoire valant le nombre de pas nécessaires à la particule pour atteindre la position n alors:
On trouve l'équation
qui est correcte.
Comme l'intégrale de cette fonction est un logarithme intégral, on peut approximer cette fonction par O(n/logn).
Quand je résoud de manière graphique, j'obtiens aussi ce résultat. Mais ce n'est pas me résultat attendu, quelqu'un pourrait il me dire ou j'ai commis une faute? Merci. (ou alors d'ou viendrait ce loglog(n))