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

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)

Citation:

---

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 ;

Citation:

---

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

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,

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

À 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 :aie:.

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 ?

Formalisons un petit peu pour appuyer mon propos :

On considère par la suite que http://chart.apis.google.com/chart?cht=tx&chl=f est effectivement continue et affine par morceau. Elle peut donc être définie par un couple de suites http://chart.apis.google.com/chart?cht=tx&chl=d et http://chart.apis.google.com/chart?cht=tx&chl=a telles que :

• Pour tout http://chart.apis.google.com/chart?cht=tx&chl=k, http://chart.apis.google.com/chart?cht=tx&chl=f est affine sur http://chart.apis.google.com/chart?c...\%20d_{k%2B1}]
• Pour tout http://chart.apis.google.com/chart?cht=tx&chl=k, http://chart.apis.google.com/chart?cht=tx&chl=f' (la dérivée de http://chart.apis.google.com/chart?cht=tx&chl=f) est constante sur http://chart.apis.google.com/chart?c...\%20d_{k%2B1}] et vaut http://chart.apis.google.com/chart?cht=tx&chl=a_k.

On note http://chart.apis.google.com/chart?cht=tx&chl=M le plus grand indice de http://chart.apis.google.com/chart?cht=tx&chl=d et http://chart.apis.google.com/chart?cht=tx&chl=a (le dernier élément), avec http://chart.apis.google.com/chart?cht=tx&chl=M potentiellement http://chart.apis.google.com/chart?cht=tx&chl=\infty.

Ainsi,
http://chart.apis.google.com/chart?c...cdot a_{k%2B1}
avec http://chart.apis.google.com/chart?cht=tx&chl=\ell le plus grand http://chart.apis.google.com/chart?cht=tx&chl=k tel que http://chart.apis.google.com/chart?cht=tx&chl=d_k\le n.

Asymptotiquement, voila ce qu'il advient :

• Si http://chart.apis.google.com/chart?c...hl=M\neq\infty,
  http://chart.apis.google.com/chart?c...-d_M)\cdot a_M qui est dominée par http://chart.apis.google.com/chart?c...chl=a_M\cdot n.
  Donc http://chart.apis.google.com/chart?c... O(a_M\cdot n).
• Si http://chart.apis.google.com/chart?cht=tx&chl=M=\infty,
  alors http://chart.apis.google.com/chart?cht=tx&chl=f est l'approximation affine par morceau d'une certaine fonction http://chart.apis.google.com/chart?cht=tx&chl=g qu'il nous reste à déterminer.

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 :aie: , 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.. :aie: scogneugneu..)

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

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

Citation:

---

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.

Citation:

---

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)

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

Citation:

---

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

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

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

Citation:

---

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

Citation:

---

Envoyé par Franck Dernoncourt

Cela dépend du genre de publications,

---

arXiv dans un premier temps..

J'avais soumis au JGT mais justement je m'étais fait jeter pour "non optimisation".. et "non-calcul de la complexité"..

Or le pbe est global, mais mon algo est justement un algo empirique..

Citation:

---

Envoyé par Franck Dernoncourt

mais normalement une complexité se démontre formellement (ce qui au préalable nécessitera de connaître la complexité de f).

---

Voir la figure plus haut.. Comment penses-tu que je pourrais trouver une valeur théorique ??? Je suis ouvert à toute sggestion.. :)

Mis à part l'intuition que "plus le nuage de points est gros, plus les segments sont petits et donc plus la "slice" est petite", donc je supposais une complexité "du style" logarithmique, je n'ai rien trouvé de particulièrement théorique pour appuyer mes dires.. D'où le tracé graphique et mes essais de déduction d'après ce graphique...

Citation:

---

Envoyé par Franck Dernoncourt

A la rigueur tu peux peut-être t'en sortir en parlant de complexité empirique.

---

C'est ce que je comptais faire.. Comme les mesures sont sur de nombreux cas différents couvrant un large domaine de N... Pas exhaustif certes, mais ....

Citation:

---

Envoyé par Franck Dernoncourt

Ensuite, cela dépend des objectifs des recherches

---

Ce n'est pas une "recherche" à proprement parler... C'est la publication d'un travail fait (et opérationnel)

Citation:

---

Envoyé par Franck Dernoncourt

(comparer la complexité avec d'autres algorithmes,

---

Entre autres, bien que ce genre d'algos n'ait pas vu sa complexité exposée pleinement (dépôts de brevet etc etc)

Citation:

---

Envoyé par Franck Dernoncourt

simplement indiquer que ton algorithme n'explose pas lorsque la taille de l'entrée augmente, etc.)

---

Oui aussi, et si possible en indiquant un ordre de grandeur de la complexité (au vu des critiques du reviewer précédent)

Citation:

---

Envoyé par souviron34

J'avais soumis au JGT mais justement je m'étais fait jeter pour "non optimisation".

---

Qu'entendaient-ils par "non optimisation" ?

Citation:

---

J'ai un critère de sélection (empirique) pour passer à travers ces points qui définit une "slice" dans ce nuage.

---

Il faudrait :

1. trouver la complexité de f : chronométrer sa vitesse d'exécution peut donner des indices intéressants, mais beaucoup de choses peuvent biaiser la vitesse (cache, swap, etc), donc mieux vaut passer par le pseudocode correspondant ;
2. avoir une estimation de la valeur retournée par f en fonction de son input : un simple graphique, même si il agrège plusieurs runs, sera toujours soupçonné de non générique, donc mieux vaut essayer d'estimer mathématiquement la taille de la slice.

Sinon je suis fatigué et j'ai lu le thread en diagonale, mais j'ai l'impression que les points 1 et 2 ne sont pas très clairement distingués dans ce thread.

Je ne connais pas l'objectif de ton article, mais c'est potentiellement un point critique, donc cela vaut certainement la peine d'analyser cela le plus possible.

Citation:

---

Envoyé par souviron34

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

---

J'ai du mal à te suivre. C'est quoi ton objectif exactement ?
Tu as un ensemble X de vecteurs x_1,...,x_n dans un R^p, et tu cherches à former une partition de X selon un critère empirique ?

Citation:

---

Envoyé par souviron34

Or le pbe est global, mais mon algo est justement un algo empirique..

Voir la figure plus haut.. Comment penses-tu que je pourrais trouver une valeur théorique ??? Je suis ouvert à toute sggestion.. :)

---

J'ai du mal à saisir ce que tu entends par "algo empirique", mais, pour la complexité... Si tu ne peux pas facilement chopper la complexité de ton algo, tu peux sûrement trouver plus facilement une borne sup/inf.

Citation:

---

Envoyé par davcha

Si tu ne peux pas facilement chopper la complexité de ton algo, tu peux sûrement trouver plus facilement une borne sup/inf.

---

Big O est en général plus facile à trouver qu'une bonne supérieure.