Discussion :

[souviron34]

Je reviens vers vous car, comme toujours, mon café du matin m'éclaircit les idées..

Si on reprend le graphe 4 donné plus haut, on a :

log ( f(N)/N ) = 1 - a log (N )

donc

f(N) = N 10^(1-a log(N))

Comment dénommerait-on la complexité d'une telle fonction ?

De même avec f(N) = 1/N et f(N) = 10^-N?

ça vous paraît sans doute évident mais moi je m'y perd dans les appellations et notations...


PS: @Davcha :

• j'ai un ensemble de points 2D
• j'ai une enveloppe de cet ensemble de points (non convexe)
• je cherche effectivement à obtenir une partition empirqiue de cet ensemble, basée sur les segments existants de l'enveloppe

@Franck : en fait, c'est un peu de la recherche, sauf que je suis seul, à mon compte, pas dans un labo ou une université ou une entreprise. Pour le reste jc'est justement pour évaluer la complexité de f que je fais ça : sa principale limitation est le nombre de points utilisés.. Quant à la "non-optimisation",j'en ai tenu compte et j'ai résolu : c'est super-optimisé partout.. (en fait, ils me critiquaient sur des parties dont des optimisations existaient, alors que ce n'était pas le coeur du pbe).

f représente le nombre de points explorés, c'est à dre la "complexité théorique" du calcul (la pratique dépend des opérations de calcul faites dedans) : f représente l'indice de boucle..

[Franck Dernoncourt]

f(N) = N 10^(1-a log(N))

Comment dénommerait-on la complexité d'une telle fonction ?

Je ne comprends pas : nous sommes bien d'accord que la valeur de f n'a aucun rapport avec sa complexité ?

[davcha]

• j'ai un ensemble de points 2D
• j'ai une enveloppe de cet ensemble de points (non convexe)
• je cherche effectivement à obtenir une partition empirqiue de cet ensemble, basée sur les segments existants de l'enveloppe

f représente le nombre de points explorés, c'est à dre la "complexité théorique" du calcul (la pratique dépend des opérations de calcul faites dedans) : f représente l'indice de boucle..

Donc, f est le cardinal de l'ensemble des points composant ton enveloppe ?

[souviron34]

Je ne comprends pas : nous sommes bien d'accord que la valeur de f n'a aucun rapport avec sa complexité ?

Vu que la valeur de f est un indice de boucle, il me semble que la complexité de l'algo s'exprime en fonction de f et de m (voir plus bas)

La complexité totale de l'algo , étant donné que c'est une double boucle, est en : m * n.. Mais n est une fonction de N : n = g(N)

pour chaque point i de m, j'ai g(i) = f(N) en moyenne, avec f(N) = expression ci-dessus : f(N) est constant pour chaque point i (puisqu'elle ne dépend que de N), la complexité totale est donc O ( m * f(N) )

Je cherche donc l'expression totale de la complexité de cette double boucle : comment peut-on la nommer, ou la borner de manière la plus proche en termes standards de compelxité ...

Donc, f est le cardinal de l'ensemble des points composant ton enveloppe ?

Non...

Pour chaque point de l'enveloppe, j'explore f points du nuage..

Ce que j'avais cité dans le premier post :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for ( i = 0 ; i < m ; i++ )
  for ( j = 0 ; j < f(N) ; j++ )

m est le nombre de pts de l'enveloppe
f est le nbe de pts explorés pour 1 pt i

Si f = N, j'ai bien une complexité en O(m N)
si f = log(N) j'ai bien une complexité en O (m log(N)), et on dit qu'on a une compleixté logarithmique

Maintenant, vu l'expression de f, comment s'exprime la complexité de cette double boucle en termes stantards de complexité ? comment on l'appelerait ? y a-t-il une manière standard de la nommer, de la définir ? ou de la borner ?

Et je repose les 2 questions plus haut en plus :

si pour chaque pt i j'ai f(N) = 1/N, comment appelerait-ton un algo un O (m 1/N) ?
de même, si pour chaque pt i j'ai f(N) = 10^-N, comment appellerait-on un algo en O ( m 10^-N) ?



En fait, la question semble être : comment dénommerait-on une complexité inverse d'une exponentielle ? (ou exponentielle avec exposant négatif). Et comment la noterait-on ?

[Franck Dernoncourt]

si pour chaque pt i j'ai f(N) = 1/N, comment appelerait-ton un algo un O (m 1/N) ?
de même, si pour chaque pt i j'ai f(N) = 10^-N, comment appellerait-on un algo en O ( m 10^-N) ?

En fait, la question semble être : comment dénommerait-on une complexité inverse d'une exponentielle ? (ou exponentielle avec exposant négatif). Et comment la noterait-on ?

Il n'y a pas vraiment de nom à ma connaissance, mais écrire simplement que f est O(m 1/N) ou O ( m 10^-N) est tout à fait acceptable : c'est une complexité comme une autre.

[souviron34]

C'est vrai ? ce serait super alors..

Parce que avec une fonction f comme :

f(N) = N 10^(1-a log(N))



si je peux exprimer la complexité comme

O( m N 10^(1-a log(N)) )

ça me termine quasiment le boulot, et je peux même facilement alors affirmer que c'est mieux que log(log(N)) (il me semble bien, non ?), donc que au piire l'algo est borné en double log ? (je ne sais plus si c'est Theta ou Big Omega ou g : faut que je vérifie)

Il me suffit de produire le graphique 4 , et la preuve empirique est évidente

Si cette expression est acceptable, alors je vais terminer ce paragraphe sur la complexité, qui est le dernier manquant à l'article..

Tu es sûr ? je pourrais bien exprimer comme O( m N 10^(1-a log(N)) ) et ce sera compréhensible et accepté du point de vue des théoriciens ?


PS: pour l'appeler, est-ce qu'un terme comme "fractional complexity" ou "reverse-exponential complexity" ou "negative-exponential complexity" ou "degressive complexity" ou "decreasing complexity" ou "reverse -proportionality complexity" ou ... serait compréhensible et approprié ?

Le facteur est ~ 1 (entre 0.5 et 0.2) jusque vers 50, ~0.1 jusque vers 500 (entre 0.2 et 0.1), ~ 0.01 (entre 0.1 et 0.01) jusque vers 50 000, ~ 0.001 après, etc...


PPS : je suis bien content de mon optimisation plus il y a de points, plus ça va proportionnellement plus vite .. YESSSSS !!

[Franck Dernoncourt]

Parce que avec une fonction f comme :

f(N) = N 10^(1-a log(N))

si je peux exprimer la complexité comme

O( m N 10^(1-a log(N)) )

Yep mais il faudrait tout de même que tu simplifies l'expression en faisant tendre N vers l'infini

Également, confirmes-tu que la complexité de f est O(1) ?

[souviron34]

Qu'entends-tu par "la complexité de f est O(1)" ??

f = fraction(N)

c'est ça ? où dans les premiers nombres c'est au max = N (en fait à 0.5 N)

Disons que sans optimisation, c'est en O(m N). Avec l'optimisation, aux faibles nombres je me retrouve avec cette complexité. Puis, plus le nombre augmente, plus ça diminue.. On le voit sur le premier graphique, et les remarques qui avaient été faites après "linéaires par morceaux".. Sur le total, on passe de O(m N), donc O(N^2) quand m ~ N (ce qui ne se passe que pour les touts petits nombres < 10), à O ( N ) quand m ~ N/10, puis à O ( m 1/N) quand m ~ N/100, etc etc...

Comme j'ai exposé à peu près le problème : la fonction f correspond au nombre de points du nuage explorés. m correspond au nombre de points de l'enveloppe.

Quand N est petit, j'explore en gros 50% du nuage restant, ce qui est le cas si j'utilise la méthode brute-force. Plus N grandit, plus j'explore une petite partie du nuage, qui se trouve limitée par le segment correspondant de l'enveloppe. : plus N grandit, plus le segment de l'enveloppe est proportionnellent petit, et donc plus son domaine d'intersection avec le nuage est petit...

ça répond à ta question ?



Maintenant, pour N infini, et comme l'exposant de la fonction est (1 - a log(N)), que vaut log(infini) ???

Mes souvenirs sont lointains , mais ça a une valeur ?? c'est pas 2 ?

ce qui donnerait N 10^(1-2a)


En fait, en relisant la page Wiki Big O notation je me demande si ça n'est pas représenté par O(n^c), sous le vocable "fractional power". Sauf qu'ils le classifient entre N et log(N)... parce que je suppose qu'ils utilisent c comme une constante... Ce qui n'est pas vraiment le cas ici.. Sauf aysmptotiquement...

[Franck Dernoncourt]

log(infini) = infini
Egalement, oublie pas que <math> b = x^\frac{1}{\log_b(x)}.</math>.

[souviron34]

log(infini) = infini

Donc si je te suis, 10-... tend vers 0, donc la limite est en O(m). OK. Mais c'est pas Omega, plutôt que O dans ce cas asyptotique ?

Parce que, par exemple, on pourrait dire :

best case : O(m) N quasi infini
worst case : O(mN) N petit
average case : O ( m N^c) avec la notation

Non ?


Sinon je ne vois pas , à part pour signifier l'asymptote, ce qu'on peut en faire...

MAis dans le cas "average" comme dans le cas Worst (et comme je pense ans le cas "best"), ce n'est pas une asymptote, c'est le vrai nombre, la vraie valeur, non ??

Egalement, oublie pas que <math> b = x^\frac{1}{\log_b(x)}.</math>.

Mes vieux neurônes n'acceptent plus tellement ce genre de gymnastique... snifff.. C'est à dire ? qu'en déduis-tu ?

[davcha]

Y'a un truc qui m'ennuie dans ton histoire souviron.

f(N) est fonction de N.
m est également fonction de N.

Ensuite, tu essaies de trouver la complexité de ton algo, que tu exprimes comme une fonction de m et N.

Et tu constates que quand N augmente, la proportion de points, par rapport à l'ensemble des points, que tu explores par point appartenant à l'enveloppe de ton nuage diminue.
Autrement dit, tu constates que quand N->infini, p->0 avec p=(points explorés)/N.

Du coup, tu en déduis que quand N augmente, ton algo devient linéaire ou quasi linéaire.

Globalement, ça veut dire que quand N->infini, tu explores un nombre constant de points pour chacun des m points appartenant à l'enveloppe.
Est-ce vrai ?

A mon avis, comme m est fonction de N, tu devrais exprimer la complexité de ton algo en fonction de N uniquement.

[Franck Dernoncourt]

m est également fonction de N.

quelle est la relation ?

[davcha]

Tu as un nuage de N points et une enveloppe de ce nuage comportant m points du nuage.

Donc, m croit avec N.

Après, pour en dire plus que ça... Faut avoir des infos sur les données de souviron.

[Franck Dernoncourt]

Je commence à m'y perdre

[souviron34]

Globalement, ça veut dire que quand N->infini, tu explores un nombre constant de points pour chacun des m points appartenant à l'enveloppe.
Est-ce vrai ?

A mon avis, comme m est fonction de N, tu devrais exprimer la complexité de ton algo en fonction de N uniquement.

L'expression d'un certain nombre d'algos, comme par exemple ceux d'enveloppe convexe, sont appelés "output-sensitive"

Wiki :

Convex hull algorithms

Optimal output-sensitive algorithms

As stated above, the complexity of finding a convex hull as a function the input size n is lower bounded by Ω(n log n). However, the complexity of some convex hull algorithms can be characterized in terms of both input size n and the output size h (the number of points in the hull). Such algorithms are called output-sensitive algorithms.

On peut donc tout à fait caractériser une complexity par son nommbre d'entrées ET son nombre de sorties..


Maintenant, en dernier point de l'article, le calcul (l'approximation) de m en fonction de N sera faite, et on aura donc une complexité purement en N (et d'un autre facteur, paramètre en pourcentage)

Au point où j'en suis du détail de l'algo, la partie que je mentionne ici n'est qu'une partie de l'algo, qui permet de passer d'une enveloppe X à une enveloppe Z plus raffinées.

Cette enveloppe X contient p points. L'enveloppe finale contiendra m points.

La boucle de i = 0 à i < m est donc bien faite pour chacun des points de l'enveloppe FINALE..

La complexité de cette partie est donc celle de cette double boucle, que , à ce stade-là, j''ai chois d'exprimer en termes croisés input-output.

Comme m dépend ultlimement de 3 facteurs ( N, un %, et un type de calcu l), mais qu'il y a plus de 5 parties dans l'algo, l'expression de m en fonction de ces facteurs se fera plus tard..

[pseudocode]

Bon, si j'ai bien compris, on a un algo en O(h.log(n)).

Ca me semble assez cohérent pour un calcul d'enveloppe, et c'est même plutot pas mal pour une enveloppe concave.

Est-ce qu'il y a une raison pour essayer de d'affiner cette formule de complexité ? Faut-il montrer que cet algo se comporte mieux qu'un autre ?

[souviron34]

Bon, si j'ai bien compris, on a un algo en O(h.log(n)).

Est-ce que

O( m N 10^(1-a log(N)) )

ou

O ( m N^c ) (l'appellation "fractional power" de la page Big O)

est cohérent avec O ( m log(N) ) ??

Lequel est mieux ?

Je pose sérieusement la question, je n'y comprend guère dans les subtilités..

Appeler m log(n), est-ce vraiment ça ? d'une part parce que ça ne correspond pas à un log, (les courbes ne sont vraiment pas similaires, de même que les ordres de grandeurs du nombre impliqué 4.4 ou 400 pour N = 50 000)), et aussi peut-être d'autre part parce que le log ne tend pas vers 0...

Penses-tu que je doive dire O ( n log(n) ) ou O ( n n^c ) ?

Ca me semble assez cohérent pour un calcul d'enveloppe, et c'est même plutot pas mal pour une enveloppe concave.

"Je veux mon n'veu"

voir PS

Est-ce qu'il y a une raison pour essayer de d'affiner cette formule de complexité ? Faut-il montrer que cet algo se comporte mieux qu'un autre ?

Ce serait certainement pas mal, donnant un argument supplémentaire de poids.... surtout pour un algo empirique fait par un physicien et non un matheux...

(les reproches qui m'avaient été faits n'étaient pas dits comme ça, mais en gros que "j'étais en dessous du niveau requis car pas assez précis et matheux" (mais je soupçonne que le reviewer en question (anonyme) était un gars qui m'avait volé l'idée et avait tenté de déposer un brevet mondial (qu'il a retiré depuis, après quelques échanges de courriers bien sentis), bien que sa réputation soit tjs là : il organise ou co-chair un certain nombres de congrès mondiaux))

Cependant ce sera la dernière phase : je suis passé à travers les diverses publications pour éliminer les méthodes à cause de leurs hypothèses diverses qui ne convenaient pas au cas général, mais je n'avais pas (à l'époque) regardé leurs complexités..



PS: d'ailleurs, quelqu'un aurait-il des références et/ou des chiffres des meilleures optimisations pour de la reconnaissance de forme, de silhouette, ou du tracking de formes ?

[pseudocode]

O ( m N^c ) (l'appellation "fractional power" de la page Big O)

est cohérent avec O ( m log(N) ) ??

Lequel est mieux ?

Et bien, log(N) est dominé par N^c.

Donc O(m log(N)) serait une "meilleure" complexité que O(m N^c ).

Penses-tu que je doive dire O ( n log(n) ) ou O ( n n^c ) ?

Il faudrait estimer la complexité de ta fonction f(). Si ce n'est de manière directe, peut-être par analogie avec un autre algorithme: divide & conquer, dichotomie, ... ?

[davcha]

Ce serait certainement pas mal, donnant un argument supplémentaire de poids.... surtout pour un algo empirique fait par un physicien et non un matheux...

(les reproches qui m'avaient été faits n'étaient pas dits comme ça, mais en gros que "j'étais en dessous du niveau requis car pas assez précis et matheux" (mais je soupçonne que le reviewer en question (anonyme) était un gars qui m'avait volé l'idée et avait tenté de déposer un brevet mondial (qu'il a retiré depuis, après quelques échanges de courriers bien sentis), bien que sa réputation soit tjs là : il organise ou co-chair un certain nombres de congrès mondiaux))

Normalement, tu as 3-5 reviewers. Ca serait vraiment con qu'il soient tous malhonnêtes.

PS: d'ailleurs, quelqu'un aurait-il des références et/ou des chiffres des meilleures optimisations pour de la reconnaissance de forme, de silhouette, ou du tracking de formes ?

Ca dépend de ce que tu appelles "meilleur". Ton algo fait du clustering ou de la classif ? Si c'est le cas, ça m'intéresse.

[souviron34]

Il faudrait estimer la complexité de ta fonction f(). Si ce n'est de manière directe, peut-être par analogie avec un autre algorithme: divide & conquer, dichotomie, ... ?

C'est ce qui a été fait plus haut .. par contre je vais regarder de plus près les Divide & Conquer, en effet..

Disons qu'en gros la question que je me pose est :

dois-je indiquer le comportement en argument principal et l'expression exacte de la compleité en détail, ou l'inverse... ?

C'est à dire dois-je dire :

"It behaves in O ( n log(n) ) (the exact equation is O (n n^c))"

ou

"It behaves in O ( n n^c ) (which in average behaves like O ( n log(n) )"

Quand on regarde les graphes, sur le 2ième on voit bien que la tendance est logarithmique (c'est presque une droite), mais pas mal bruitée, et surtout avec les "features" des ruptures de pentes qu'avaient notées Davcha. Sur le 4ième par contre, c'est beaucoup plis linéaire et moins bruité, et les "ruptures" sont réparties de part et d'autre de la moyenne...

Je m'excuse de mon pointillisme, mais je veux être irréprochable sur ce point du calcul et de la revendication de la complexiité

Normalement, tu as 3-5 reviewers. Ca serait vraiment con qu'il soient tous malhonnêtes.

Dans le cas de ce journal, c'était 1 (j'ai son rapport)... Et pas de bol...

Ca dépend de ce que tu appelles "meilleur". Ton algo fait du clustering ou de la classif ? Si c'est le cas, ça m'intéresse.

Ni l'un ni l'autre.. Il fait du "contouring", mais le plus réaliste possible, c'est à dire correspondant à la perception visuelle qu'on a du nuage..

Si je posais ces questions, c'est que vu la vitesse, simplicité du code, et expression de la complexité, j'aimerais terminer en conclusion par le fait que cela pourrrait facilement être appliqué dans ces domaines.