Discussion :

[souviron34]

Bonjour

Voilà. n'étant pas fort sur la théorie de la complexité, je me pose 2 questions existentielles :

• Pourquoi peut-on lire dans [ame="http://en.wikipedia.org/wiki/Convex_hull_algorithms"]http://en.wikipedia.org/wiki/Convex_hull_algorithms[/ame], au paragraphe Akl-Toussaint heuristics :
  
  

  These four points form a convex quadrilateral, and all points that lie in this quadrilateral (except for the four initially chosen vertices) are not part of the convex hull. Finding all of these points that lie in this quadrilateral is also O(n), and thus, the entire operation is O(n).

  ?
  
  Si je ne me trompe pas, si on a :
  
  

  Code :

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

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

  la complexité est O(N*M).
  
  Or pour savoir si un point est dans un polygone de M sommets, il faut bien faire un calcul en O(M), non ?
  
  Donc pourquoi disent-ils ça dans ce paragraphe ?
  
  
  
• Si j'ai :
  
  

  Code :

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

  1
  2
  3
  4
  5
  6
  7
  8
   
  for ( i = 0 ; i < N ; i++ )
  {
  }
   
  for ( j = 0 ; j < M ; j++ )
  {
  }

  La complexité sera bien O(N) + O(M), non ?
  
  Donc si M << N, la complexité totale sera O(N) ?
  

Merci à tous de m'éclairer...

[pseudocode]

These four points form a convex quadrilateral, and all points that lie in this quadrilateral (except for the four initially chosen vertices) are not part of the convex hull. Finding all of these points that lie in this quadrilateral is also O(n), and thus, the entire operation is O(n).

la complexité est O(N*M).

Or pour savoir si un point est dans un polygone de M sommets, il faut bien faire un calcul en O(M), non ?

Tout a fait. Et ici M=4 (quadrilatère).

La complexité est donc O(N*4) == O(N)

[souviron34]

simplement parce que M est connu ?

J'avoue avoir un peu de mal..

Quand M n'est pas connu, on dit O(M*N)

Quand M est connu on dit O(N) ?????


Si donc j'ai un algo du style :

Code :

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

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

où M est connu, je dis que c'est O(N) ??


Si M = 6, moi j'aurais dit O(6*N) et non O(N)..

Qu'est-ce que je rate dans le raisonnement ?




Par contre, ça m'arrangerait bien si je pouvais dire que c'est O(N)

[pseudocode]

simplement parce que M est connu ?

J'avoue avoir un peu de mal..

Quand M n'est pas connu, on dit O(M*N)

Quand M est connu on dit O(N) ?????

C'est pas le fait qu'il soit connu, mais qu'il soit majoré par une constante. Ici il est même égal à une constante (4).

Ca serait différent si M dépendait de N.

Si M = 6, moi j'aurais dit O(6*N) et non O(N)..

Qu'est-ce que je rate dans le raisonnement ?

O(6*N) est équivalent à O(N)

Une fonction F est en O(N) si elle est majorée par k.N, ou k est une constante. Donc si ta complexité est majorée par 6.N, elle est en O(N).

[souviron34]

Ah !! Merci tout s'éclaire..

C'était la question de majoration qui m'échappait..


Maintenant autres questions du même style :


Si j'ai :

Code :

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

1
2
3
Etape 1 : O(N)
 
Etape 2 : O(M log(M))

1. Si je sais que M << N, alors la complexité totale est O(N) ?
   
   
2. Si M dépend de N, que le pire cas est M = N - 4, le meilleur M = 0, et la moyenne M = N/100, ce serait O(N log(N)) le pire cas et O(N) la moyenne ?

[pseudocode]

Si j'ai :

Code :

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

1
2
3
Etape 1 : O(N)
 
Etape 2 : O(M log(M))

La compléxité totale est donc majorée par k1.N + k2.M.log(M), elle meme majorée par K.N + K.M.log(M) (avec K=max(k1,k2))

Donc la compléxité totale est O(N+M.log(M))

1. Si je sais que M << N, alors la complexité totale est O(N) ?

Mathématiquement, on ne peut pas en dire plus. La relation M<<N peut te permettre de dire que M.log(M) est "plus ou moins" négligeable devant N. Mais ca reste subjectif.

2. Si M dépend de N, que le pire cas est M = N - 4, le meilleur M = 0, et la moyenne M = N/100, ce serait O(N log(N)) le pire cas et O(N) la moyenne ?

hum. Comme précédemment, la complexité totale reste O(N+M.log(M)). Ce n'est pas "mathématiquement" modifiable, meme en connaisant les ordres de grandeurs de M par rapport a N.

[souviron34]

La compléxité totale est donc majorée par k1.N + k2.M.log(M), elle meme majorée par K.N + K.M.log(M) (avec K=max(k1,k2))

Donc la compléxité totale est O(N+M.log(M))



Mathématiquement, on ne peut pas en dire plus. La relation M<<N peut te permettre de dire que M.log(M) est "plus ou moins" négligeable devant N. Mais ca reste subjectif.



hum. Comme précédemment, la complexité totale reste O(N+M.log(M)). Ce n'est pas "mathématiquement" modifiable, meme en connaisant les ordres de grandeurs de M par rapport a N.

Ok.. ça me va..

O(N+Mlog(M)) << O(N*log(N))


Je crois que je tiens quelque chose..

Dans le cas du calcul d'une enveloppe convexe, si M est le nombre de sommets de l'enveloppe convexe et N le nbe de points, les meilleurs algos sont en O(N*log(M)). (O(N) ne marche que pour des polygones concaves "simples")

Je crois que j'ai trouvé un algo marchant en O(N+M(log(M)) ...