[Complexité] Encore une question de complexité
Bonjour à tous..
Je reviens vous voir pour un problème d'établissement de complexité théoique... Je m'y perds et je ne sais pas comment la nommer..
Alors voilà le problème : soit un algo ayant 2 variables N et m, comme suit :
Code:
1 2 3 4 5 6
| for ( i = 0 ; i < m ; i++ )
{
..
for ( j = 0 ; j < f(N) ; j++ )
...
} |
f(N) est croissant avec N (du style log, ou log^i, mais avec une partie bien moins pentue que le log au départ, presque linéaire), mais f(N)/N est décroissant avec N, et se comporte grosso-modo comme 1/N.
Comment dois-je exprimer la compleité : O ( m X )
Mon problème est formaliser le X..
Alors j'ai un peu la tête à l'envers et je vous demande votre aide avisée :)
Je pensais un truc comme O ( m log^i N), (où log^i est le log itéré), mais je n'arrive pas à le tracer correctement sur un graphique pour en faire la preuve..