Seu próximo nível começa aqui
Seu desenvolvimento não pode ter limites. Garanta sua Assinatura Ilimitada e libere uma preparação completa com os melhores professores do Brasil.
Sobre análise de complexidade e algoritmos de ordenação, analise as assertivas a seguir...
Sobre análise de complexidade e algoritmos de ordenação, analise as assertivas a seguir:
I. A notação O (big-O) define um limite superior assintótico: f(n) = O(g(n)) se, e somente se, existem constantes c > 0 e n₀ ≥ 1 tais que 0 ≤ f(n) ≤ c·g(n) para todo n ≥ n₀.
II. O Merge Sort apresenta complexidade Θ(n log n) no pior, no melhor e no caso médio, mantendo esse desempenho independentemente da distribuição de entrada.
III. O algoritmo Quick Sort com estratégia de pivô aleatório (randomized quicksort) possui complexidade Θ(n log n) no pior caso, eliminando completamente a possibilidade de comportamento quadrático.
IV. Se um algoritmo tem complexidade O(n²), então ele também tem complexidade O(n³), pois toda função limitada superiormente por c·n² também é limitada superiormente por c·n³ para n suficientemente grande.
Quais estão corretas?
A
Apenas I e II.
B
Apenas II e III.
C
Apenas II e IV.
D
Apenas I, II e IV.
E
Apenas I, III e IV.