※ 引述《owokko (天天都是好心情)》之铭言： : 问题: : 在有限的范围内(0,0)~(x,x) x为极大的数 : (0,0) ┌───→ x : 在这个范围内有K的大小不一的矩形 及一个点 │ : │ : 请找出包含该点的所有矩形 │ : ↓ : y : 虽然这是暴力法 不过时间复杂度只要 O(K) : 但是似乎有方法可以更快 提示是 quadtree : ( http://en.wikipedia.org/wiki/Quadtree ) : 关键好像是资料结的应用 : 不过我怎麽想时间复杂度都不会低於O(K) : 想请问各位的想法?? 献丑猜一下 :p 下面的方法：纯就 "search" 来说，复杂度是O(logK) 但是我在建立资料结构时，做了O(KlogK)的动作 (这动作不算是search嘛 :p) 往後每次有新的点要判断包含在哪些矩形内时 只需要O(logK)的时间 倘若有n个点要判断，暴力法的时间复杂度是O(nK) 这个方法则只要O(KlogK + nlogK)。 方法的细节写在这里： http://sandwichc.blogspot.com/2007/04/k-pp-quadtree.html 大意是：把矩形先排序好 (这样有犯规吗?:p) 再从排完的矩形中做蒐寻 -- My blog: http://sandwichc.blogspot.com/ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.169.117.15 ※ 编辑: sandwichC 来自: 218.169.117.15 (04/07 14:14)