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