|
9#
楼主 |
发表于 2013-10-7 09:01:33
|
只看该作者
最野蛮也是最简单的办法:一个一个比。6 s% x ~/ l6 |8 i
. c1 D. s% W! D7 H/ \
string1: TACGGCATGGCTATCGTAGCTAG; ~- ?( U' c; r3 H- k; T) T
, U5 p% f' c' `. @' }* Q
string2: GCTAT5 _6 B5 C. ]; u$ B% d
" S& O' {5 [3 s要求在string1里找到string2的位置,如果存在多个的话,都要找出来。 ) A4 h" a, Z F$ _; R
- k2 h+ ?" H, d$ [8 a拿string2和string1比,至少需要比string1的长度减去string2的长度再加1次。在实际应用中,如果string1的长度是10^9,而string2只有一二百,那么做一次基本上就是比10^9次。当然如果很幸运,string2在string1开始的地方,那一次就够了。所以平均来说,要比10^9/2次,也就是O(10^9)。 }0 f' K! c$ {; h1 h
! A4 L" u: K" c, A
但是如果实际情况中,有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年!!!人都死几次还没比完,太郁闷了,所以不可接受。
' _, X2 w# G, n& G) z' z1 [+ o& r$ A/ I0 Q- k- w% R. E: a
那如果是这个样子
) m/ c6 H' p" o& p1 {2 D$ M
/ D1 `& W" f2 I6 x; g1 Fstring1: AAAAAATTTTCCCCCGGGTTTTAAAACCCCCCGG4 Y$ i5 k' i. Y3 a0 I, i
string2: TTAAA. m" b! Z8 w, ]
7 N4 x$ ~& [; T6 G2 U3 a% r% s
是不是会快很多?
. A# @7 o* M- B0 v2 }% R, U g3 y7 i( w3 n6 J
继续扛。 |
|