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 : Sélectionner tout - Visualiser dans une fenêtre à part
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..