MO640 - Questão para a prova oral

Número: 043

Enunciado:
Sobre o algoritmo de comparação otimizado no espaço entre duas seqüências de tamanhos m e n, é incorreto afirmar que:

1. O espaço requerido é O(m+n).
2. O alinhamento ótimo é obtido através de uma estratégia de divisão e conquista.
3. Ao invés de uma matriz m×n, é utilizado um vetor de tamanho min(m,n) para o cálculo da similaridade entre as seqüências.
4. O tempo de processamento deste algoritmo aproximadamente dobra em relação à do algoritmo não otimizado.
5. NDA

Autor(a): Vinícius Geraldo Felix