作者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