Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESGRANRIO 2006
Algoritmos e Estrutura de DadosAlgoritmos
- Código
- cg025139
- Banca
- CESGRANRIO
- Órgão
- DECEA
- Ano
- 2006
- Nível
- Médio
- Cargo
- Técnico de Defesa Aérea e Controle de Tráfego Aéreo - Análise de Sistemas
Seja T um texto e C, uma cadeia de caracteres, onde n e m correspondem ao tamanho de T e C, respectivamente. Sobre a busca de C em T, é correto afirmar que o algoritmo de:
- Aforça bruta (ingênuo) tem o melhor desempenho, por utilizar funções hash.
- BKnuth-Pratt-Morris, no pior caso, tem complexidade de tempo O(log n).
- CKnuth-Pratt-Morris realiza comparações da direita para a esquerda.
- DRabin-Karp, no melhor caso, tem complexidade de tempo (mn2).
- EBoyer-Moore utiliza as heurísticas do mau caractere e do bom sufixo.