Discussion :

[souviron34]

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..

[prgasp77]

Bonjour.

Si f(N) ~ a/N alors la complexité de ton algo est en O(a.m/N).

On est bien d'accord que lorsque tu dis que f se comptorte grosso modo comme 1/N, cela signifie que f(N)*N tend vers a ?

Cdlt,


edit : (je pense que j'ai mal compris ton message)

[souviron34]

On est bien d'accord que lorsque tu dis que f se comptorte grosso modo comme 1/N, cela signifie que f(N)*N tend vers a ?

oui, tout à fait..

Cependant ;

Si f(N) ~ a/N alors la complexité de ton algo est en O(a.m/N).

est faux, puisque f(N) augmente avec N, ce qui est contredit par cette expression..

en fait, on a :

O ( m f(N) )

où f(N) augmente avec N, mais f(N)/N diminue.

Dans l'algo, je peux mesurer f(N). Je connais N et je constate ces résultats, que j'avais intuitevement trouvés : plus N augmente, plus la proportion de N que j'utilise est petite.. Le nombre effectif est cependant croissant, bien que tendant aysmptotiquement vers une limite..

Donc la complexité sera quelque chose comme O (m g(N)) où g est une fonction croissante mais décroissante en valeur relative : c'est pour ça que je pensais à log^i N ..

[prgasp77]

Au temps pour moi. Et est-il possible d'avoir l'expression de f (si elle est exprimable) ou un graphe ou une table de valeurs ? Je serais heureux de chercher avec toi une expression g qui soit utilisable.

Cdlt,

[souviron34]

Alors voilà des graphes (l'expression n'est pas estimable suivant une équation : c'est un nombre de points sélectionnés dans un ensemble, suivant une borne sur les coordonées)

Les 3 premiers repésentent seulement le f(N) en fonction de N, suivant diverses échelles (linéaire-linéaire pour le premier, log en X pour le seond, log des 2 axes pour le 3ième)

Le dernier représente le f(N)/N, en échelle LOGARITHMIQUE sur les 2 axes. La courbe verte est le 1/N

[prgasp77]

À voir tes graphes je me dis que tu as atteins les limites de la notation en grand o. Il s'agit en effet d'une complexité asymptotique ; qui ne s'intéresse qu'au comportement vers l'infini. Hors il semble que f soit approximable par une fonction linéaire par morceau.

Par définition, la notation en grand o ne peut être représentative que pour le dernier morceau de f, s'il existe. Il te sera toujours possible de trouver une fonction g qui a un comportement proche de f, mais alors g sera équivalente audit dernier morceau de f, s'il existe.

La question est donc, ce dernier morceau existe-t-il ? Si non, alors le problème reste valide (on peut trouver g tel que la complexité de ton algo O(m g(N)) soit pertinente. Si oui, alors je dirais que tu cours après une chimère .

Je n'ai pas la moindre idée de comment déterminer si f se comporte affinement à partir d'un certain N. Serait-il possible de s'intéresser à la répartition des points à partir desquels est défini f ?

[davcha]

l'expression n'est pas estimable suivant une équation : c'est un nombre de points sélectionnés dans un ensemble, suivant une borne sur les coordonées

Mais ces points ont une distribution qui suit une loi, non ?...