给定 BLAST 的时间复杂度是多少？
What is the time complexity of the given BLAST?
这是 BLAST（基本局部比对搜索工具）图。如何计算它的时间复杂度？
BLAST算法步骤：
正在创建查询序列长度为 W 的单词列表。
在数据库中搜索W字
命中序列的延长，即找到的序列，以及分配分数。这些序列将由局部比对给出。
采用所谓的 HSP（高分段对）。
第一步耗时O(n)，其中n是序列中元素的数量。
第二步是对第一步中创建的词（上界n）进行另一个循环，所以时间O(n)
第三步分配命中分数。这只能逐个字母地完成，因此时间复杂度为 O(n*m)，其中 m 是查询词中的字母数。作为上限，我们可以说时间是 O(n^2)
第四步简单循环得到分数，所以一直O(n)。
总之，该算法可以同化为 O(n^2)，在 m << n 的情况下，我们可以说 O(n*m)。下限是 O(n).
这是 BLAST（基本局部比对搜索工具）图。如何计算它的时间复杂度？
BLAST算法步骤：
正在创建查询序列长度为 W 的单词列表。
在数据库中搜索W字
命中序列的延长，即找到的序列，以及分配分数。这些序列将由局部比对给出。
采用所谓的 HSP（高分段对）。
第一步耗时O(n)，其中n是序列中元素的数量。
第二步是对第一步中创建的词（上界n）进行另一个循环，所以时间O(n)
第三步分配命中分数。这只能逐个字母地完成，因此时间复杂度为 O(n*m)，其中 m 是查询词中的字母数。作为上限，我们可以说时间是 O(n^2)
第四步简单循环得到分数，所以一直O(n)。
总之，该算法可以同化为 O(n^2)，在 m << n 的情况下，我们可以说 O(n*m)。下限是 O(n).