빠른 걸림 최악의 경우

QHull (그리고 아마도 다른 좋은 구현 인 QuickHull)은 많은 경우 잘 작동합니다. 그러나 이론적으로 최악의 경우는 O (n^2) 일 수 있습니다. 실제로 나는 QHull이 제대로 작동하지 않는 많은 차원 (예 : 20 또는 100)의 수치 예제를 보지 못했습니다.빠른 걸림 최악의 경우

QHull이 제대로 작동하지 않거나 잘못된 결과를 제공하는 수치 예제 또는 여기에 적용 할 수없는 내용을 알고 있습니까?

출처

2013-12-07 Alef

"많은 데이터 포인트"를 의미합니까? AFAIK quickhull은 2 차원 데이터 전용입니다. - Wikipedia에 따르면, 최악의 경우는 O (n²)이고, O (n log n)은 평균입니다. –

위키 백과 : "대칭성이 높거나 원의 둘레에 점이있는 경우 처리가 일반적으로 느려집니다." –

어느 쪽이든, 많은 데이터 요소 및/또는 많은 차원. 사실 최악의 경우는 O (n^2)입니다. 감사. 나는 그 질문을 편집했다. – Alef

다차원의 경우 A. Donda가 말한 것을 일반화해야합니다. P의 각 Point p에 대해 norm (p) == 1 인 점 P를 생성합니다. convex hull은 P입니다 (두 점이 동일하지 않으면) ~ O (n^2)의 잘못된 실행 시간을 초래합니다.

2D 케이스의 경우 구면의 3D 점에 대해 원의 점을 선택합니다.

출처

2013-12-07 18:43:59 Daniel

답변

관련 문제