[問題] 樹狀結構的應用

看板C_and_CPP (C/C++)作者 (笨小孩)時間11年前 (2014/11/01 12:30), 編輯推噓2(208)
留言10則, 5人參與, 最新討論串1/1
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) VC++ 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) OPENCV 問題(Question): 之前用過像K-D TREE等演算法 拿來分群用 這裡想請教各位大大 在高維度(3維以上) TREE的搜尋 建置等操作是否比暴力法還慢呀? 那這樣是否代表樹狀結構 比較不套用在 高維度的資料應用上? 懇請各位大大 指導 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.237.42 ※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1414816238.A.75F.html

11/01 12:39, , 1F
想先反問你 linear search比quick sort還快 為什麼
11/01 12:39, 1F

11/01 12:40, , 2F
我們要先排序之後再用binary search?
11/01 12:40, 2F

11/01 13:33, , 3F
我看過它時間複雜度,一維確實快,但資料維度越高越
11/01 13:33, 3F

11/01 13:33, , 4F
慢,線性搜索卻保持O(n)
11/01 13:33, 4F

11/01 22:30, , 5F
kd-tree 目前我摸索的結果是你說的沒錯, 所以有 bbf 改良
11/01 22:30, 5F

11/02 08:53, , 6F
所以高維度的資料,用線性搜索較好?
11/02 08:53, 6F

11/02 09:44, , 7F
我覺得是看你要找幾次 要找很多次的話先排序比較好
11/02 09:44, 7F

11/02 11:39, , 8F
所以對於高維度度的資料來說,tree
11/02 11:39, 8F

11/02 11:39, , 9F
的用途不是在搜索?
11/02 11:39, 9F

11/02 13:57, , 10F
主要還是看你樹長得好不好. 還有查詢的頻率跟方式
11/02 13:57, 10F
文章代碼(AID): #1KL67kTV (C_and_CPP)
文章代碼(AID): #1KL67kTV (C_and_CPP)