[問題] 兩數列的比較

看板Prob_Solve作者 (Ar藤)時間15年前 (2008/09/05 15:36), 編輯推噓7(7推 0噓 14→)
留言21則, 5人參與, 最新討論串1/1
小弟不知道這問題是否有名字 問題如下 一長數列長度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
推
09/05 21:21, , 1F
dynamic time wraping
09/05 21:21, 1F
→
09/06 00:50, , 2F
DTW是可拉長縮短的
09/06 00:50, 2F
→
09/06 00:51, , 3F
我的是pattern多長 對到的就多長 不用做長度變化
09/06 00:51, 3F
※ 編輯: Arton0306 來自: 140.114.229.83 (09/06 00:52) ※ 編輯: Arton0306 來自: 140.114.229.83 (09/06 00:53)
→
09/06 00:54, , 4F
這樣一樣是往dtw的方向查嗎
09/06 00:54, 4F
推
09/06 07:24, , 5F
抱歉我沒有搞清楚 XD 不過他們應該都算是sequence alignment
09/06 07:24, 5F
→
09/06 20:09, , 6F
OK 謝謝
09/06 20:09, 6F
推
09/08 19:22, , 7F
開101個stack 分別對應0~101
09/08 19:22, 7F
→
09/08 19:24, , 8F
讀到片段中的數字 再丟入編號為該數字的stack
09/08 19:24, 8F
→
09/08 19:25, , 9F
丟入新讀到的片段數字 丟掉過時的片段末數字
09/08 19:25, 9F
→
09/08 19:27, , 10F
判斷101個stack與n個數字的異同 101*m -> O(m)
09/08 19:27, 10F
推
09/09 22:46, , 11F
樓上的能不能回一篇完整一點的 @@" 這樣我看不是很懂
09/09 22:46, 11F
→
09/09 22:46, , 12F
麻煩了，多謝...
09/09 22:46, 12F
→
09/11 10:08, , 13F
LinkCar 的解法在 "找對應到的數列" 這部分是 O(m)
09/11 10:08, 13F
→
09/11 10:08, , 14F
但若還要計算 euclidean distance, 我想 O(mn) 還是跑不
09/11 10:08, 14F
→
09/11 10:09, , 15F
掉 XD (除非文中所述的的 euclidean distance 跟我所想
09/11 10:09, 15F
→
09/11 10:10, , 16F
的是不一樣的東西…) :p
09/11 10:10, 16F
推
09/11 10:17, , 17F
yoco315, LinkCar 大概是筆誤; 你把 "stack" 換成
09/11 10:17, 17F
→
09/11 10:18, , 18F
"int array" 大概就能看懂了
09/11 10:18, 18F
推
09/11 21:52, , 19F
對 只是個counter而已 而且也不一定是101 題目剛好
09/11 21:52, 19F
推
09/11 21:55, , 20F
請問題目中的euclidean distance為何意思??
09/11 21:55, 20F
→
09/11 21:59, , 21F
查完資料了解了，是我沒弄懂原本題意
09/11 21:59, 21F
‣ 更多 Arton0306 的文章
文章代碼(AID): #18mE6DpP (Prob_Solve)