Questão 802912

• Banca: CESPE / CEBRASPE
• Órgão: INMETRO
• Ano: 2010
• Provas: CESPE - 2010 - INMETRO - Pesquisador Tecnologista - Metrologia em Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos; Conceitos Básicos e Algoritmos

Considerando que A seja um algoritmo, {E₁, ..., E_m} o conjunto de todas as entradas possíveis de A, e t_i o número de passos efetuados por A quando a entrada for E_i , assinale a opção correta.

• A. A complexidade do caso médio é igual ao máximo
  
  
• B. A complexidade do melhor caso é igual ao mínimo
  
  
• C. Se a complexidade do algoritmo A que resolve o problema P é O(l), então A é denominado algoritmo ótimo para P.
  
• D. A complexidade do pior caso é a somatória de t_i × p_i até m, em que p_i é a probabilidade de ocorrência da entrada E_i .
  
  
• E. Se a complexidade do algoritmo A que resolve o problema P é O(m), então A é denominado algoritmo de caso médio para P.
  

Gabarito: C