|
9#

楼主 |
发表于 2013-10-7 09:01:33
|
只看该作者
最野蛮也是最简单的办法:一个一个比。- x. L- N: x9 \+ U) R
8 r# k* r" g L
string1: TACGGCATGGCTATCGTAGCTAG2 P! W( j9 g, r3 I e s) l# y, u
: q- f; L: |% r' Jstring2: GCTAT' b5 i, ]/ E, {
' @ S; l% E+ R3 k- h! P" I; }要求在string1里找到string2的位置,如果存在多个的话,都要找出来。 4 @$ @0 d' Y% e3 z1 @$ s
8 j! e5 r+ U: R& y9 r
拿string2和string1比,至少需要比string1的长度减去string2的长度再加1次。在实际应用中,如果string1的长度是10^9,而string2只有一二百,那么做一次基本上就是比10^9次。当然如果很幸运,string2在string1开始的地方,那一次就够了。所以平均来说,要比10^9/2次,也就是O(10^9)。9 a6 X: b* Y' f( w6 y
, h9 R' l* E9 p, n% S
但是如果实际情况中,有10^6到10^9个string2s,那总共要比多少次?10^15到10^18次。这什么概念?不考虑所有的overhead,比一次只需一个时钟,那3G的CPU,意味着一秒可以比10^9次,要完成这样一个工作,需要10^6到10^9秒,1年=365天 x 24小时 x 3600秒=31Millon秒。也就是说,最短大约需要12天,最长需要30年。如果这样的操作做十次,一台CPU要算至少120天到300年!!!人都死几次还没比完,太郁闷了,所以不可接受。+ ], P6 k0 [: v) `3 t' P
/ ? L7 z! X: {' ~( k: ]6 C3 y F
那如果是这个样子
( f, ?+ [1 O; z
& c' n+ {2 \5 E F9 Dstring1: AAAAAATTTTCCCCCGGGTTTTAAAACCCCCCGG S: O: x8 @" k( ]4 U
string2: TTAAA( n" `! n3 h7 x' Y0 F
# E2 g t+ Z X. ~# e" Q是不是会快很多?& h; h0 s; q7 X
3 O, @4 R, n9 s8 o
继续扛。 |
|