[Complexité] Encore une question de complexité

**souviron34** · 15/05/2012, 14h12

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** · 15/05/2012, 14h20

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** · 15/05/2012, 14h39

Envoyé par prgasp77

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 ;

Envoyé par prgasp77

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** · 15/05/2012, 15h09

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** · 15/05/2012, 17h07

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** · 15/05/2012, 19h15

À 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 ?

**prgasp77** · 15/05/2012, 19h55

Formalisons un petit peu pour appuyer mon propos :

On considère par la suite que $f$ est effectivement continue et affine par morceau. Elle peut donc être définie par un couple de suites $d$ et $a$ telles que :

Pour tout $k$ , $f$ est affine sur $[d_k\ ;\ d_{k+1}]$
Pour tout $k$ , $f'$ (la dérivée de $f$ ) est constante sur $[d_k\ ;\ d_{k+1}]$ et vaut $a_k$ .

On note $M$ le plus grand indice de $d$ et $a$ (le dernier élément), avec $M$ potentiellement $\infty$ .

Ainsi,
$f(n) = (n-d_\ell)\cdot a_\ell\,+\,\sum_{k=0}^{\ell}\,m_{k+1}\cdot a_{k+1}$
avec $\ell$ le plus grand $k$ tel que $d_k\le n$ .

Asymptotiquement, voila ce qu'il advient :

Si $M\neq\infty$ ,
$\forall n>d_M,\ f(n)\,=\,f(d_M)\ +\ (n-d_M)\cdot a_M$ qui est dominée par $a_M\cdot n$ .
Donc $f(n) = O(a_M\cdot n)$ .
Si $M=\infty$ ,
alors $f$ est l'approximation affine par morceau d'une certaine fonction $g$ qu'il nous reste à déterminer.

**souviron34** · 16/05/2012, 00h45

Je comprend à peu près (quoique la notation aM-n j'ai un peu de mal).

En ce qui concerne la notation O et les valeurs asymptotiques, ce n'est pas ce que j'ai compris : ce que tu donnes me semble être la définition de la complexité mathématique. D'après ce que j'ai compris (mais j'ai peut-être mal compris, pour moi ces théories, bien que compréhensibles en gros, me semblent complexes), la complexité algorithmique ne s'occupe pas des asymptotes (sauf éventuellement avec ?? theta ou g ??). La complexité d'un tri en O(n logn) n'est pas une complexité asymptotique mais "moyenne", "normale"..

Maintenant, quand je regarde les graphes 3 et 4, je me dis :

log (f(n)) = a log(N) + b (à peu près, bien que assez bruité, et la fin semble "saturer")
log ( f(n)/N ) = -a' log(N) + b' (vraiment plus cohérent pour tous les points)

On doit bien pouvoir tirer l'expression de f(N) en fonction de N, non ??

Note : une partie plus ou moins linéaire jusque vers 100 peut s'expliquer aisément comme un cas particulier, si besoin est... J'avoue que la partie qui semblerait linéaire jusque vers 2500 me laisse perplexe.. En fait, je voyais un peu, avant d'avoir tracé les graphes (mais dans la réalité il doit y avoir continuité) une formule comme :

N < 10 f(N) ~ N
N < 100 f(N) ~ log(N) (ou peut-être N/10 ou N/100)
N < 1000 f(N) ~ log(log(N)) (.......)
N < 10000 f(N) ~ log(log(log(N))) (...)
...

Disons que ce serait logique par rapport au problème..

Maintenant, au vu des graphes, d'une part les 3 et 4 donnent ce que j'ai indiqué plus haut, d'autre part avec le 1, on a assez l'impression qu'il est divisé en 3 parties, que je verrais plus log que linéaires... Mais dans la partie "arrondie" du log, qui du coup est presque droite

, mais, que çe soit ça ou une fonctionn affine par morceau, ça me semble trop compliqué de trouver comme ça, et injustifié dans l'algo d'avoir des "zones" distinctes.. alors qu'avec les graphes 3 et 4 il me semble que l'on a 2 équations de base qui devraient être solubles (bien que la solution m'échappe.. scogneugneu..)

**souviron34** · 16/05/2012, 11h44

en fait, en prenant on café ce matin, et en regardant le graphe 1 et 2, je me demande si ça ne pourrait pas se formaliser comme :

O ( log^x N )

le x étant soit log(N), soit log^* (N)

Il semble qu'il y ait des ruptures de courbes aux alentours du milieu des intervalles, vers 50, 500, 5000, 50000, et qu'entre ce soit du style logarithmique..

Je vais de ce pas vérifier ça..

**souviron34** · 16/05/2012, 15h12

Bon

je progresse un peu...

Voici un nouveau graphe : en bleu le f(N) mesuré, en rouge une courbe correspondant à :

f(N) ~ log(N), N < 50
f(N) ~ log^2(N) N < 500
f(N) ~ log^3(N) N < 5000
f(N) ~ log^4(N), N < 50000
f(N) ~ log^5(N) N >= 50000

C'est bien à peu près ça, sauf que les sauts sont inversés, et les pentes dans le mauvais ordre (les plus pentues là où ça devrait être le moins, et réciproquement)..

Une idée à partir de ça ??

**pseudocode** · 16/05/2012, 19h46

Envoyé par souviron34

La complexité d'un tri en O(n logn) n'est pas une complexité asymptotique mais "moyenne", "normale"..

Heu... si. La notation O() est la complexité asymptotique. Elle permet de créer une relation d'ordre.

Son but n'est pas d'approximer le nombre réel d'opérations, mais de montrer qu'un algo se comporte "mieux" qu'un autre.

f(N) ~ log(N), N < 50
f(N) ~ log^2(N) N < 500
f(N) ~ log^3(N) N < 5000
f(N) ~ log^4(N), N < 50000
f(N) ~ log^5(N) N >= 50000

Ton algo se comporte donc mieux qu'un algo en log(log(n)).

F(N) = O(log log N)

**souviron34** · 17/05/2012, 11h02

Salut Xavier

Ben je crois pas

.. Le log^x N était la puissance x du log et non le log itéré x fois..

D'après le graphe, ça aurait l'air entre log^2 et log^3.. si j'ai bien suivi mes propres formules.. ^^ ..

Mais j'ai eu une autre idée ce matin.. Je vais vérifier ça aujourd'hui et je vous reviens là-dessus...

**davcha** · 17/05/2012, 14h11

Envoyé par souviron34

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

**souviron34** · 17/05/2012, 15h07

je crois que c'est cette loi que je recherche

En fait, le fond du problème est :

J'ai un nuage de points (non aléatoirement) répartis.
J'ai un critère de sélection (empirique) pour passer à travers ces points qui définit une "slice" dans ce nuage.
Je cherche, pour une publication, l'expression du nb moyen de points de cette "slice" en fonction de N..

Si je prend l'exemple d'une enveloppe convexe : je cherche le nombre moyen de points définis par la projection d'un segment de l'enveloppe sur le nuage..

Ce qui me chiffone, c'est qu'avec le 4ième graphe du premier post, on devrait arriver à s'en sortir, mais je m'y perd :

log ( f(N)/N ) = a log (N ) + b

avec a négatif..

**souviron34** · 17/05/2012, 17h55

Pensez-vous que, pour une publication, un graphe comme celui-ci pourrait être suffisant pour appuyer une affirmation d'une complexité en O(log(log(N)) ?? (même log(N) me suffirait, mais tant qu'à faire

En rouge : les mesures

En mauve : log(N) mis à l'échelle

En bleu : log(log(N)) mis à l'échelle

Le problème est présenté dans la deuxième figure... Les mesures correspondent au nombre moyen de points figurant dans la "slice"..

**Franck Dernoncourt** · 17/05/2012, 20h34

Envoyé par souviron34

Pensez-vous que, pour une publication, un graphe comme celui-ci pourrait être suffisant pour appuyer une affirmation d'une complexité en O(log(log(N)) ?

Cela dépend du genre de publications, mais normalement une complexité se démontre formellement (ce qui au préalable nécessitera de connaître la complexité de f). A la rigueur tu peux peut-être t'en sortir en parlant de complexité empirique. Ensuite, cela dépend des objectifs des recherches (comparer la complexité avec d'autres algorithmes, simplement indiquer que ton algorithme n'explose pas lorsque la taille de l'entrée augmente, etc.)

**souviron34** · 17/05/2012, 22h08