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 :
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.
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++ ) ... }
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..
Partager