MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Qual das alternativas abaixo é verdadeira?

1. Se utilizarmos um algoritmo Θ(n³)  para encontrar a medianas no SELECT então este não mais terá tempo linear no pior caso
2. Se o QUICKSORT for modificado para realizar o particionamento da mesma forma que o SELECT o faz, então o tempo no pior caso seria O(nlgn)
3. Se o arranjo fosse dividido em 3 grupos o SELECT ainda teria tempo linear no pior caso
4. O SELECT é a melhor opção para se aplicar em problemas práticos
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - QUESTÃO PARA PROVAL ORAL

Número:

Enunciado: Dada uma sequência de entrada <a₁, a₂,...,an>. Sobre o tempo de execução (T(n)) do Quicksort é possível afirmar:

1. Se an > ai então T(n) = Θ(n²), para i = {1...n-1}
2. Se ai = ai+1 então T(n) = Θ(nlgn), para i = {1...n-1}
3. Se ai < ai+1 então T(n) = Θ(n), para i = {1...n-1}
4. Se ak < an < a(n/2)+k então T(n) = O(n lg n), para k = {1...(n/2)-1}
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - QUESTÃO PARA PROVAL ORAL

Número:

Enunciado: Sejam a ≥ 1 e b > 1 constantes, seja f(n) uma função e T(n) definida sobre os números inteiros não negativos pela recorrência

T(n) = aT(n/b) + f(n)

É INCORRETO  afirmar que: 

1. Se a = b e f(n) = n então T(n) = Θ(n lg n)
2. Se a = b² e f(n) = n então T(n) = Θ(n²)
3. Se a = b e f(n) = n²  então T(n) = Θ(n²)
4. Se a = b²  e f(n) = n² então T(n) = Θ(n lg n) 
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dadas as funções $f(n)$, $g(n)$ assinale a alternativa CORRETA:

1. Se $f(n)=\omicron(g(n))$ então $\underset{n\rightarrow \infty}{\lim}\frac{f(n)}{g(n)}>0$
2. Se $f(n)=\omega(g(n))$ então $\underset{n\rightarrow \infty}{\lim}\frac{f(n)}{g(n)}<0$
3. Se $f(n)=\Theta(g(n))$ então $\underset{n\rightarrow \infty}{\lim}\frac{f(n)}{g(n)}\leq\infty$
4. Se $f(n)=O(g(n))$ então $\underset{n\rightarrow \infty}{\lim}\frac{f(n)}{g(n)}\geq0$
5. NDA

Ideia original de: Anderson Carlos 

Objetivo do blog

Este blog tem como objetivo auxiliar na aprendizagem de complexidade de algoritmos, através do desenvolvimento de questões sobre o tema.