|
9#
楼主 |
发表于 2013-10-7 09:01:33
|
只看该作者
最野蛮也是最简单的办法:一个一个比。3 Z5 p0 C5 k1 o5 K/ ]
s, X; |: S: `3 X) Zstring1: TACGGCATGGCTATCGTAGCTAG+ `; s) h$ o& L! Y% A
6 j+ n! b2 b1 d& f1 istring2: GCTAT
0 j7 e+ v6 h$ o5 y, V# T z
v4 V$ o# ~9 K要求在string1里找到string2的位置,如果存在多个的话,都要找出来。
6 F, O/ G" {/ m0 G8 V I2 S" ~. N9 u8 z! g9 h7 P
拿string2和string1比,至少需要比string1的长度减去string2的长度再加1次。在实际应用中,如果string1的长度是10^9,而string2只有一二百,那么做一次基本上就是比10^9次。当然如果很幸运,string2在string1开始的地方,那一次就够了。所以平均来说,要比10^9/2次,也就是O(10^9)。
! p8 [8 q7 ~9 a1 a% T. Z$ O1 G( y' x9 j/ y
但是如果实际情况中,有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年!!!人都死几次还没比完,太郁闷了,所以不可接受。6 I5 J. q( a5 T |- p
+ z- f, R) I4 D/ a% `/ Y
那如果是这个样子9 S- k2 H/ u3 \% y, ^& f
0 E! b1 {! @( P0 ]3 b
string1: AAAAAATTTTCCCCCGGGTTTTAAAACCCCCCGG" n/ m- ^; E2 Y, V3 t
string2: TTAAA4 J l k$ W7 n2 M
: }; S$ j8 F1 f0 ?" Q是不是会快很多?
8 b6 ?, M- e$ M9 v" J
5 I% m3 `2 K# i1 E" |- w8 R2 u" j继续扛。 |
|