作者Arton0306 (Ar藤)
看板Prob_Solve
標題[問題] 兩數列的比較
時間Fri Sep 5 15:36:44 2008
小弟不知道這問題是否有名字
問題如下
一長數列長度m 如
3 5 4 2 1 4 3 5 1
一短數列長度n 如
3 4 5
求 短數列對應到長數列的哪片段 會有最小的euclidean distance
像這個例子 會對到
3 5 4 2 1 4 3 5 1
3 4 5
3 4 5
數字範圍0~100的整數
100000>m>1000 10000>n>10
m>n
想問是否有比O(mn)更好的算法??
感謝!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.229.83
1F：推 DJWS:dynamic time wraping 09/05 21:21
2F：→ Arton0306:DTW是可拉長縮短的 09/06 00:50
3F：→ Arton0306:我的是pattern多長 對到的就多長 不用做長度變化 09/06 00:51
※ 編輯: Arton0306 來自: 140.114.229.83 (09/06 00:52)
※ 編輯: Arton0306 來自: 140.114.229.83 (09/06 00:53)
4F：→ Arton0306:這樣一樣是往dtw的方向查嗎 09/06 00:54
5F：推 DJWS:抱歉我沒有搞清楚 XD 不過他們應該都算是sequence alignment 09/06 07:24
6F：→ Arton0306:OK 謝謝 09/06 20:09
7F：推 LinkCar:開101個stack 分別對應0~101 09/08 19:22
8F：→ LinkCar:讀到片段中的數字 再丟入編號為該數字的stack 09/08 19:24
9F：→ LinkCar:丟入新讀到的片段數字 丟掉過時的片段末數字 09/08 19:25
10F：→ LinkCar:判斷101個stack與n個數字的異同 101*m -> O(m) 09/08 19:27
11F：推 yoco315:樓上的能不能回一篇完整一點的 @@" 這樣我看不是很懂 09/09 22:46
12F：→ yoco315:麻煩了，多謝... 09/09 22:46
13F：→ AmosYang:LinkCar 的解法在 "找對應到的數列" 這部分是 O(m) 09/11 10:08
14F：→ AmosYang:但若還要計算 euclidean distance, 我想 O(mn) 還是跑不 09/11 10:08
15F：→ AmosYang:掉 XD (除非文中所述的的 euclidean distance 跟我所想 09/11 10:09
16F：→ AmosYang:的是不一樣的東西…) :p 09/11 10:10
17F：推 AmosYang:yoco315, LinkCar 大概是筆誤; 你把 "stack" 換成 09/11 10:17
18F：→ AmosYang:"int array" 大概就能看懂了 09/11 10:18
19F：推 LinkCar:對 只是個counter而已 而且也不一定是101 題目剛好 09/11 21:52
20F：推 LinkCar:請問題目中的euclidean distance為何意思?? 09/11 21:55
21F：→ LinkCar:查完資料了解了，是我沒弄懂原本題意 09/11 21:59