Teste

1)Algoritmo de complexidade 3n³
Tempo T = 3000
Problema de tamanho x

Algoritmo mais rápido de complexidade 2n²
Maquina 6vezes mais rápida
Qual tempo para resolver problema de mesmo tamanho

3n³ = 3000 2.n² = x n³ = 3000 / 3 2.10² = x n = raiz cubica de 1000 n = 10

f(n) = 3n² + 6n f(n) = O(n²) f(n) = ≤ C x n² Ѵ n² ≥ n0
3n² + 10n ≤ Cn² Ѵ n ≥ n0
Ѵ n ≥ 1, 10n ≤ 10n²
3n² + 10n ≤ 3n² + 10n² Ѵ n ≥ 1 ≤ 13n² C = 13 f(n) = n² + 6n g(n) = n² f(n) = O(g)

6n ≤ n x n Ѵ n ≥ 6
6n ≤ n² Ѵ n ≥ 6 n² + 6n ≤ n² + n² Ѵ n ≥ 6 ≤ 2n² C = 2
Recursividade

Algo: potencia 2
Entrada: n € N e n ≥ 0
Saida: 2 elevado a N

Se n = 0 entao Retorne 1
Senão
Retorne 2 * pot2(n-1)

Algo: soma
Entrada: n € N e n ≥ 1
Saida: 5n

Se n = 1 entao Retorne 1
Senão
Retorne n + soma(n-1)

Algo: Fatorial duplo
Entrada: n € N e n ≥ 1
Saida: Fatorial duplo de n

Se n = 1 entao Retorne 1
Senão
Se n = 2 entao Retorne 2 Senão Retorne n*faltorial duplo(n-2)

Considere um algoritmo A e um algoritmo B com funções de complexidade de tempo A(n) = n² – n + 449 e B(n) = 49n + 49 . Determine quais são os valores de n pertencentes ao conjunto dos números naturais para os quais os algoritmos A e B apresentam o mesmo desempenho, respectivamente.

n² + n + 449 = 49n + 49 n² - n + 449 – 49n – 49 = 0 bascara b² - 4.a.c

Um algoritmo tem complexidade n3 . Num certo computador, num tempo t = 1000, resolve um problema de tamanho x. Imagine agora que você tem disponível um algoritmo mais rápido, de complexidade 2n2 e uma máquina cinco vezes mais rápida. Que tempo esse segundo algoritmo precisará para resolver o mesmo problema de tamanho x nessa máquina mais rápida?

Computador 1 Computador 2 f(n) = n³ t = 2n² / 5 t = n³ t = 2x10² / 5
1000 = x³ t = 40
X = raiz cubica de 1000
X = 10