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. 如何解決復發A（n）= A（n-1）+ n * log（n）？
- 11. 時間複雜度O（N日誌（log n）的）+ N O（L）
- 12. 如何計算O（Log（N））？
- 13. 時間複雜度 - O（n^2）到O（n log n）搜索
- 14. 圖形搜索O（log（N）（N + M）
- 15. 與log（n）相比，log（n^2）的大O是什麼？
- 16. 通用實用的排序算法比O（n log n）快嗎？
- 17. 複製關係：T（n/16）+ n log n
- 18. 顯示遞歸關係是O（n log n）
- 19. 尋找關於如何計算O（n log n）的複雜度的例子？
- 20. 複雜度O（log（n））是否等於O（sqrt（n））？
- 21. 證明log（n！）是Ω（n log（n））
- 22. 快速帶O的最壞的情況下（N log n）的
- 23. O（log n）中的二叉搜索樹？
- 24. O（n log n）是否有簡寫術語？
- 25. NHibernate 3.2 LINQ n + 1解決方案
- 26. Django N + 1查詢解決方案
- 27. 解決非齊次線性遞推關係（log n）的時間
- 28. 如何解決：T（N）= T（N - 1）+ N
- 29. 解決一個復發的關係T（N）= T（N-√N）+1
- 30. 「移動」 - 博客 - 任何想法/現有解決方案？
TLE？超時限制？ – sehe 2011-06-10 09:39:23