SóProvas

ID
17842
Banca
CESGRANRIO
Órgão
BNDES
Ano
2008
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Se a complexidade de tempo de um algoritmo é da ordem de Θ (n log n), é correto afirmar que esse algoritmo também é

Alternativas
Comentários
  • Se tivermos uma lista de N números e quisermos encontrar algum deles assume-se que a complexidade no melhor caso é f(N) = ? (1), pois assume-se que o número estaria logo na cabeça da lista. Na questão o f(N) é f(n log n), portanto, ? (n log n)
  • ômega(g(n)) --> melhor casoTheta(g(n)) --> caso médioO(g(n)) --> pior casoSe eu sei que um algoritmo é do tipo ???(nlog(n)), posso afirmar que esse é também um algoritmo de Theta(nlog(n)). Ele também pode ser um algortimo de caso médio ou pior caso, porém mesmo que ele seja um algoritmo de caso médio ou pior caso, necessariamente ele deve também ser um algoritmo de melhor caso desse mesmo tipo. É um problema de raciocínio lógico e envolve o conhecimento das notações de melhor, médio e pior caso.
  • Essa questao deve ser feita por exclusão. A unica opcao que podemos ter como correta é a letra C
    Lembrando que Teta é Caso Medio; Omega é Melhor Caso e "o" maiusculo o Pior Caso.
    E a ordem crescente de compelxidade é: O(1); O(logn); O(n); O(nlogn); O(n^2) ...

    a) um algoritmo nao pode ter dois casos medios diferentes
    b) o melhor caso de um algoritmo nao pode ter complexidade maior que o caso medio
    c) podemos afirmar isso.
    d) o pior caso de um algoritmo nao pode ter complexidade melhor que o caso medio
    e) o pior caso de um algoritmo nao pode ter complexidade melhor que o caso medio

  • COMENTARIO DA 5