UAM - Estrutura de dados - Prova N2 - Pergunta 6

Prévia do material em texto

UAM - Estrutura de dados - Prova N2
Pergunta 6
A tarefa de obter uma expressão matemática para avaliar o tempo de execução de um algoritmo não é simples, mesmo considerando-se uma expressão aproximada (SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de Dados e seus Algoritmos. 3. ed. Rio de Janeiro: Ltc, 2010). As expressões são representadas por meio de funções, no qual podemos descobrir a complexidade do algoritmo. Desta forma, analise as afirmativas abaixo.
I. O algoritmo Bubble Sort não é um algoritmo estável.
II. O algoritmo Bublle Sort, possui complexidade O (n) para o melhor caso e O (n2) para o pior caso.
III. O algoritmo Quick Sort possui complexidade O (n log (n)) para o melhor caso.
IV. O algoritmo Quick Sort é um algoritmo estável.
Julgue e assinale se as afirmativas acima são verdadeiras (V) ou falsas (F).
· F, F, V, F.
· F, F, V, V.
· V, F, F, F.
· V, F, V, V.
· F, V, V, F.