|
9#

楼主 |
发表于 2013-10-7 09:01:33
|
只看该作者
最野蛮也是最简单的办法:一个一个比。/ p8 y/ U* r5 l* o; p) S9 a! O
1 M" c. N) Q! h5 P; a( V/ I
string1: TACGGCATGGCTATCGTAGCTAG8 P% [$ J9 o2 j9 E
1 I) F+ h- S3 c2 b, A) J. x1 ostring2: GCTAT9 R( Y, s" f' E* V6 f" x0 M) N
* \, K# ?; y5 N$ m( E
要求在string1里找到string2的位置,如果存在多个的话,都要找出来。
0 T8 K: P+ n2 [3 w8 V/ o0 V: i0 ^
拿string2和string1比,至少需要比string1的长度减去string2的长度再加1次。在实际应用中,如果string1的长度是10^9,而string2只有一二百,那么做一次基本上就是比10^9次。当然如果很幸运,string2在string1开始的地方,那一次就够了。所以平均来说,要比10^9/2次,也就是O(10^9)。) S g# {; q3 }/ Z+ B5 x
; q1 ]$ j0 ?( `0 T, _% ^$ H H
但是如果实际情况中,有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年!!!人都死几次还没比完,太郁闷了,所以不可接受。
; o4 D, m+ z. {; C* K& |5 W, b1 L5 m. w7 P/ V5 O4 p2 E6 t6 \; e0 z
那如果是这个样子
; w' L( J L3 n8 x* L/ ], d
& Q! Y2 b+ N) W% sstring1: AAAAAATTTTCCCCCGGGTTTTAAAACCCCCCGG
# y$ Y- K K7 k. O6 u% pstring2: TTAAA
+ S6 J! W2 r8 R! \5 ?3 J
/ Z, N2 e* ~5 s# e; X! Q! \是不是会快很多?
2 T- f& Q& O- U( S
: v. u% A8 K6 w0 t继续扛。 |
|