Métodos de Resolução de Recorrências

Questions and Answers

Qual é a definição formal da notação o?

f(n) = o(g(n)), para todo c > 0 e n0 | f(n) < c.g(n), para todo n > n0. (correct)

f(n) = o(g(n)), para algum c > 0 e n0 | f(n) ≥ c.g(n), para todo n > n0.

f(n) = o(g(n)), para todo c > 0 e n0 | f(n) = c.g(n), para todo n > n0.

f(n) = o(g(n)), para todo c > 0 e n0 | f(n) < c.g(n), para todo n < n0.

Qual dos seguintes limites é um exemplo de o?

n3 = o(n2)

2n = o(n2) (correct)

2n2 = o(n2)

3n = o(n2)

O que é a análise assintótica?

Um modo de simplificar código em linguagens de programação.

Uma técnica para medir o tempo de execução em hardware específico.

Um método para avaliar a complexidade de algoritmos no pior caso. (correct)

Uma forma de implementar algoritmos de forma mais eficiente.

Qual das seguintes notações é utilizada para denotar a complexidade superior de um algoritmo?

Notação O Signup and view all the answers

Qual afirmativa é verdadeira sobre o limite 2n²?

2n² = O(n²) é assintoticamente firme. Signup and view all the answers

Quando se diz que um limite é assintoticamente não firme?

Quando o limite não cresce na mesma taxa. Signup and view all the answers

Quais as características da notação Θ na análise assintótica?

É utilizada para descrever limites superior e inferior de uma função. Signup and view all the answers

Qual das seguintes afirmações sobre a notação Ω é verdadeira?

Indica um limite inferior para a complexidade de algoritmos. Signup and view all the answers

Qual é a relação correta entre as notações O e o?

O é sempre mais restritivo que o. Signup and view all the answers

No contexto de algoritmos, o que a notação o indica?

Define que uma função cresce mais rapidamente que outra, mas não atinge o limite superior. Signup and view all the answers

Qual a principal característica de um algoritmo recursivo?

Contém uma chamada recursiva a si próprio. Signup and view all the answers

Qual o objetivo das recorrências em algoritmos?

Analisar o tempo de execução em termos de entradas menores. Signup and view all the answers

Qual dos seguintes métodos não é utilizado para resolver recorrências?

Análise de Fluxo Signup and view all the answers

O que ocorre quando um algoritmo possui uma chamada recursiva a si próprio?

Seu tempo de execução pode ser descrito por uma equação de recorrência. Signup and view all the answers

Qual da seguintes afirmações sobre o cálculo do fatorial é verdadeira?

A função executa T(n - 1) para calcular fatorial de n. Signup and view all the answers

Qual o impacto do uso de ferramentas matemáticas na solução de recorrências?

Permitem estabelecer limites sobre o desempenho do algoritmo. Signup and view all the answers

Qual é a relação entre o tempo de execução de um algoritmo recursivo e o tamanho do problema?

O tempo de execução para um problema maior pode ser expresso em termos de problemas menores. Signup and view all the answers

Qual é a finalidade do Teorema Mestre nas recorrências?

Ajudar na análise do tempo de execução de recursões específicas. Signup and view all the answers

Qual é a expressão que representa a complexidade do algoritmo MERGESORT?

$T(n) = 2T(n/2) + cn$ Signup and view all the answers

Qual método permite visualizar a iteração de uma recorrência?

Método da Árvore de Recursão Signup and view all the answers

Qual é o número de níveis em uma árvore de recursão para um problema de tamanho n?

$ ext{log}_2(n) + 1$ Signup and view all the answers

Qual é a complexidade de tempo do algoritmo MERGESORT?

$O(n ext{log} n)$ Signup and view all the answers

Em qual método se utiliza a estrutura de árvore para resolver recorrências?

Método da Árvore de Recursão Signup and view all the answers

Qual expressão representa o limite quando k tende a infinito na recorrência apresentada?

$n(1 - (1/3)^k)$ Signup and view all the answers

Qual dos seguintes métodos não é mencionado como uma forma de resolver recorrências?

Método de Comparação Signup and view all the answers

Qual é a principal aplicação do Método da Árvore de Recursão?

Para resolver recorrências em algoritmos de divisão e conquista Signup and view all the answers

Qual valor de n deve ser considerado para provar que $n^2 + 10n$ está em $O(n^2)$?

n > 10 Signup and view all the answers

Qual é a condição necessária que deve ser satisfeita para que $9n + 9$ esteja em $O(n^2)$?

n > 1 Signup and view all the answers

Para qual valor de n a afirmação $100n o O(n^2)$ se torna válida?

n > 100 Signup and view all the answers

Qual expressão correta formula a validação de $2n^3 + 100n$ em $O(n^3)$?

$2n^3 + 100n o 102n^3$ Signup and view all the answers

A função $log n$ é um exemplo de qual notação assintótica?

O(n) Signup and view all the answers

Qual a prova que sustenta que $n^{1.5} o O(n^2)$?

$n^{1.5} o n^2$ Signup and view all the answers

Qual é o maior valor de c que pode ser usado na definição de $f(n) o O(g(n))$, conforme a expressão $n^2 + 10n$?

10 Signup and view all the answers

Qual a propriedade incorreta a respeito de $2n^{3} + 100n$ estar em $O(n^{3})$?

Prova usa $2n^3 + 100n o 10n^3$. Signup and view all the answers

Qual expressão justifica que $n^2 + 10n$ está em $O(n^2)$ para n > 10?

$1 + rac{10}{n} o 2$ Signup and view all the answers

Com a função $f(n) = 2n^2 + 3n + 4$, qual é a relação correta com $g(n) = n^2$?

$f(n) o O(g(n))$ é verdadeiro. Signup and view all the answers

O que se deve considerar ao determinar se uma função pertence a $O(g)$?

Valores de c e n0 que satisfazem a desigualdade $f(n) o c imes g(n)$. Signup and view all the answers

Qual é a notação correta que indica que $n o O(n^2)$?

$n$ cresce mais lentamente que $n^2$. Signup and view all the answers

Para uma função estar em $O(n imes log n)$, qual é uma condição que deve ser verdadeira?

A função deve crescer mais lento que qualquer potência de n. Signup and view all the answers

Study Notes

Definição de Recorrências

Algoritmos recursivos são aqueles que chamam a si mesmos, cujo tempo de execução é descrito por equações de recorrência.
A recorrência relaciona a execução do algoritmo para um problema de tamanho n com a execução sobre entradas menores.