038-2008

MO640 - Questão para a prova oral
Número: 038
Enunciado:
Sobre o algoritmo básico e a sua adaptação para espaço linear é correto afirmar que:

1. Usamos um algoritmo de divisão e conquista para o cálculo da similaridade.
2. O algoritmo básico é altamente recomendado para alinhar sequências longas devido a redução do espaço.
3. A complexidade de tempo assintótica para o cálculo da similaridade entre as sequências é de O(mn) para os dois algoritmos.
4. Sobre a complexidade de tempo assintótica para a construção dos alinhamentos ótimos, o básico realiza em O(mn) enquanto o de espaço linear realiza em O(n+m).
5. NDA

Autor(a): Victor de Abreu Iizuka