|
9#
楼主 |
发表于 2013-10-7 09:01:33
|
只看该作者
最野蛮也是最简单的办法:一个一个比。
- J; z. l9 u1 i4 Y& f' E, ]' i9 o" H5 {7 ^7 v2 b: G% k- }/ o
string1: TACGGCATGGCTATCGTAGCTAG" q( w Z$ L! w% J0 Y! r, P
( Z% J' V! ~) z4 o: jstring2: GCTAT
# F: U- f! c# |: l0 w' N. r: i/ d2 |/ s' G) D: ?
要求在string1里找到string2的位置,如果存在多个的话,都要找出来。
H$ y, p* R! Q7 }$ N3 s, G6 J
) _, a: d, j/ f1 f/ _0 X拿string2和string1比,至少需要比string1的长度减去string2的长度再加1次。在实际应用中,如果string1的长度是10^9,而string2只有一二百,那么做一次基本上就是比10^9次。当然如果很幸运,string2在string1开始的地方,那一次就够了。所以平均来说,要比10^9/2次,也就是O(10^9)。 |, U, V; w: n' G+ s7 S
. l& ]% k: _3 z! @7 `
但是如果实际情况中,有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年!!!人都死几次还没比完,太郁闷了,所以不可接受。# T0 m/ T" X$ k7 X. `" a5 i8 d- o* P
' _3 {, E! {; ?3 O! Y
那如果是这个样子
8 q- Q8 \* |' ]$ v, Q0 P3 n
8 E9 F/ \ L) }/ g( }, Q: p! estring1: AAAAAATTTTCCCCCGGGTTTTAAAACCCCCCGG
' B3 Q- w2 C+ Q3 `string2: TTAAA% Q% D& u! K& M) F- B5 s
* v3 C6 P8 E/ k T/ G
是不是会快很多?6 W! C9 a6 @9 W9 M8 H
0 E8 y* O/ h0 s继续扛。 |
|