Complexidade assintótica

Question 1

Complexidade assintótica

Answer 1

Método para comparar dois algorítimos e saber qual é o melhor.
Trabalho com problemas em que a entrada é grande ou muito grande.

Question 2

Metodologia para resolver a Complexidade assintótica:

F(x) = 9n^2 + 7n

Answer 2

1 - SEPARO cada termo
2 - Para cada termo:
2.1 - ELIMINAR a de MENOR complexidade: ISOLAR as CONSTANTES multiplicativas.
2.2 - COMPARAR as funções RESTANTES OBTENDO a função que CRESCE MAIS RAPIDAMENTE.

Question 3

1 - ELIMINAR a de MENOR complexidade: ISOLAR as CONSTANTES multiplicativas.

F(x) = 9n^2 + 7n

Answer 3

9n^2 -> n^2
7n -> n

n^2 e n

Question 4

2 - COMPARAR as funções RESTANTES obtendo a função que cresce mais rapidamente.

n^2 e n

Answer 4

n^2 cresce mais rapidamente do que n, quando aumento o valor de n

Menos explosivo para o mais explosivo
1 < log n < n < n log n < n^2 < 2^n < N! (Fatorial)…

Question 5

Quantas e Quais as notações de limite?

Answer 5

Ó - Limite Superior
teta - Limite Superior Justo
Omega - Limite inferior

Question 6

Limite Ó ou … ?

Answer 6

Limite Superior
Chute pra cima
(Big anotation - notação de complexidade assintótica)
g(n) = O f(n) 
O f(n) tem que ser >= g(n)

Question 7

Limite teta ou … ?

Answer 7

Limite Superior Justo

O mais próximo possível

Question 8

Limite Omega ou … ?

Answer 8

Limite inferior

Chute pra baixo