Ciência de Dados - Algoritmos de Las Vegas

Qual é o problema abordado no texto?

• Ordenação de conjuntos

• Busca de elementos

• Classificação de dados

• Cálculo de médias

Quantos passos básicos são descritos no método do Quicksort para o problema de ordenação?

• 4

• 1

• 2

• 3

O que é feito no passo de escolher um elemento denominado pivô no Quicksort?

• Permutação dos elementos

• Particionamento do conjunto

• Concatenação dos subconjuntos

• Ordenação dos elementos

Qual é a função que particiona os elementos do conjunto de acordo com o pivô no Quicksort determinístico?

• PARTIÇÃO-RAND

• QUICKSORT-RAND

• QUICKSORT

• PARTIÇÃO

No Quicksort randomizado, como é escolhido o pivô em comparação com o Quicksort determinístico?

• Sempre o último elemento

• Sempre o primeiro elemento

• Aleatoriamente

• O maior elemento

Qual é a complexidade do Quicksort determinístico no pior caso?

• O(n log n)

• O(log n)

• O(n)

• O(n^2)

O que é utilizado para determinar a mediana de um conjunto no Quicksort determinístico?

• Método de divisão

• Método de particionamento

• Escolha aleatória

• Método de ordenação

Qual é o procedimento principal no Quicksort randomizado?

• QUICKSORT-RAND

• PARTIÇÃO-RAND

• QUICKSORT

• PARTIÇÃO

O que representa a variável aleatória X no Quicksort randomizado?

• Número de partições

• Número de iterações

• Número de trocas de elementos

• Número total de comparações

Qual é o valor esperado do número de comparações efetuadas pelo algoritmo no Quicksort randomizado?

• O(n^2 log n)

• O(n log n)

• O(n)

• O(n^2)