Re: [問題] 如何找出包含某點的所有矩形 ?
※ 引述《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)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 4 篇)：