3
我試過了spoj問題http://www.spoj.pl/problems/GANNHAT/，但是我的O（n^2）解決方案給了TLE.Can任何人都可以給我一些關於這個問題的O（n log n）解決方案。我無法弄清楚它是如何實現的可以在O（n log n）.Thanx中完成。有關http://www.spoj.pl/problems/GANNHAT/的O（n log n）解決方案的任何想法？
A
回答
1
1
我已經有了一個解決方案，複雜度最多可以是O（nlogn），但最壞的情況是O（n^2）。
它基於quadtrees。一旦建立了樹，就很容易知道什麼是最接近某個特定點Ai的點，只需遍歷鄰居即可。您不必迭代「遠」，因爲只要您在相鄰單元中找到點Aj，就可以消除更遠處單元中的大部分其他點。
編輯：嗯，我剛看到傑夫回答，四叉樹只是KD樹與K = 2，但它們適合你的問題，因爲該點是在2D =）
相關問題
- 1. Javascript：將解決方案更改爲O（n log n）
- 2. 是log（n！）= O（（log（n））^ 2）？
- 3. 這是否解決O（N log（N））時間中的3SUM？
- 4. floor（√2n）的O（log log n）算法？
- 5. 算法K-Way合併。這個解決方案是O（n log k）嗎？
- 6. 大O符號 - O（n日誌（N））對O（的log（n^2））
- 7. 該算法是否有O（N）解決方案？
- 8. 你如何看出O（log n）和O（n log n）之間的差異？
- 9. 如何製作O（N）算法解決方案？
- 10. 顯示n^2不是O（n * log（n））？
- 11. 如何解決復發A（n）= A（n-1）+ n * log（n）？
- 12. 爲O（n^log n）的碰撞檢測
- 13. 時間複雜度O（N日誌（log n）的）+ N O（L）
- 14. 如何計算O（Log（N））？
- 15. 時間複雜度 - O（n^2）到O（n log n）搜索
- 16. 爲什麼此循環返回值爲O（n log log n）而不是O（n log n）？
- 17. 圖形搜索O（log（N）（N + M）
- 18. 如何修改我的方法來搜索並刪除O（N）或O（N * log N）中的重複項？
- 19. 河內的解決方案比O（2^n）好？
- 20. 求解W（n）= W（n/2）+ n log n？
- 21. 與log（n）相比，log（n^2）的大O是什麼？
- 22. log（n！）=Ω（n * log（n））？
- 23. 通用實用的排序算法比O（n log n）快嗎？
- 24. 顯示遞歸關係是O（n log n）
- 25. 複製關係：T（n/16）+ n log n
- 26. 這個解決方案的時間複雜度是O（N）還是O（LogN）？
- 27. 有沒有算法的時間複雜度爲O（sqrt（n）* log（n））？
- 28. 尋找關於如何計算O（n log n）的複雜度的例子？
- 29. AVL Tree給我O（c^n）而不是O（log n）
- 30. 複雜度O（log（n））是否等於O（sqrt（n））？
TLE？超時限制？ – sehe 2011-06-10 09:39:23