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 :
la complexité est O(N*M).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 for ( i = 0 ; i < N ; i++ ) for ( j = 0 ; j < M ; j++ )
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 :
La complexité sera bien O(N) + O(M), non ?
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++ ) { }
Donc si M << N, la complexité totale sera O(N) ?
Merci à tous de m'éclairer...
Partager