Questão 2001680

Tecnologia da Informação · 2022

Questão

ID 2001680

Disciplina: Tecnologia da Informação

Assuntos: Complexidade de Algoritmos (Big-O, P x NP)

Ano: 2022 Banca: Fundação de Apoio à Educação e Desenvolvimento Tecnológico de Minas Gerais - Fundacao CEFETMINAS Órgão: Instituto Federal da Bahia

Sobre complexidade de algoritmos é INCORRETO afirmar:

Alternativa A:
Um algoritmo exponencial no tempo de execução tem função de complexidade O(cⁿ),c>1.
Alternativa B:
Um algoritmo polinomial no tempo de execução tem função de complexidade O(p(n)), onde p(n) é um polinômio.
Alternativa C:
Algoritmos polinomiais são geralmente obtidos mediante entendimento mais profundo da estrutura do problema.
Alternativa D:
A distinção entre algoritmo exponencial e algoritmo polinomial torna-se irrelevante quando o tamanho do problema a ser resolvido cresce.
Alternativa E:
Algoritmos polinomiais são muito mais úteis na prática do que os exponenciais.