NEW
Font size
WorksheetsCiência de Dados - Complexidade Computacional
Total questions: 10
Worksheet time: 20mins
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
