Ciência de Dados - Complexidade Computacional

Qual é a definição de complexidade de melhor caso de um algoritmo?

• O valor máximo dentre todas as complexidades assintóticas do algoritmo

• O valor mínimo dentre todas as complexidades assintóticas do algoritmo

• O valor médio dentre todas as complexidades assintóticas do algoritmo

• O valor médio dentre todas as complexidades assintóticas do algoritmo

O que é a notação ˝ utilizada no estudo de complexidade?

• Expressa valores justos de complexidades

• Expressa valores de complexidades médias

• Expressa limites inferiores

• Expressa limites superiores

O que define se um algoritmo é considerado eficiente?

• Complexidade linear

• Complexidade polinomial

• Complexidade logarítmica

• Complexidade exponencial

O que é a classe de problemas P na teoria da complexidade computacional?

• Problemas tratáveis que admitem algoritmo polinomial

• Problemas intratáveis que não admitem algoritmo polinomial

• Problemas que não possuem solução

• Problemas que não foram classificados

O que é a classe de problemas NP-completo?

• Problemas que não possuem solução

• Problemas que não foram classificados

• Problemas que admitem certificados verificáveis em tempo polinomial

• Problemas que possuem solução em tempo exponencial

O que é necessário para que um problema seja considerado tratável na teoria da complexidade computacional?

• Existência de um algoritmo exponencial

• Existência de um algoritmo logarítmico

• Existência de um algoritmo polinomial

• Existência de um algoritmo linear

O que é a classe de problemas N P na teoria da complexidade computacional?

• Problemas intratáveis que não admitem algoritmo polinomial

• Problemas que não possuem solução

• Problemas que não foram classificados

• Problemas tratáveis que admitem algoritmo polinomial

O que é uma transformação polinomial entre problemas de decisão?

• Uma transformação que preserva a natureza exponencial do algoritmo

• Uma transformação que preserva a natureza polinomial do algoritmo

• Uma transformação que aumenta a complexidade do problema

• Uma transformação que diminui a complexidade do problema

Qual é a importância da classe NP-completo na teoria da complexidade computacional?

• Define problemas de decisão

• Define problemas tratáveis

• Define problemas sem solução

• Define problemas intratáveis

O que é a complexidade de caso médio de um algoritmo?

• Complexidade para o pior caso de execução

• Complexidade para a média de todas as entradas possíveis

• Complexidade para entradas pequenas

• Complexidade para o melhor caso de execução