20/09/2019 estrutura de dados 1

Introdução à notação assintótica e análise de algorítimos

1Ghz= 10⁹ operações (1 bilhão)
1Gi=10 ^ (20)

comparando algorítimos com complexidade de tempo diferentes em relação ao tamanho da entrada
tamanho de entradas a1=10²,a2= 10³, a3=10⁶, a4=10⁹

análise é ver o tempo,memória consumida,dados transferidos entre núcleos, etc em função do tamanho da entrada
ex criando uma função no formato T(n), sendo T o tempo em nº de instruções


f(n)=O(g(n))
significa que f(n) é limitada assintoticamente superiormente por g(n)
ou seja, "maior ou igual"
f(n)<=C*g(n) a partir de um momento n0 (sendo C uma constante)

definição: sejam  f,g funções com domínio nos naturais e contradomínio nos reais não negativos
				f,g: |N -> |R+
				escrevemos que f(n) = O(g(n)) se existe um n0 natural e uma constante C real não negativa tal que todo f(n) seja menor ou igual que C*g(n) para todo n>=n0


se for limitada superior mente por uma constante, f(n)<=k, então f(n)<=C*1, ou seja,: f(n)=O(1)
e O(1)+O(1) = O(1)
-----------------------------------------------------------------------------------------------------
T(n) <= O(1) +
		somatório com i=1 até i =n de O(1) +
		O(1) +
		somatório de i=0 até i=n-1 de 2Tb(n) + O(1)

ob: Tb(n) é logarítmico O(log n)

T(n) = O(n) + somatório de i=0 até i=n-1 de 2 O(log n)
	= O(n) + nO (log n) = O (n * log n)

obs: nO (log n) = O (n log n)

f(n) = O (n)
g(n) = O (n log n)

f(n) + g(n) = O(n) + O (n log n)
			= O ( n log n) + O ( n log n)
			= O (n log n)
-----------------------------------------------------------------------------------------------------

descobrir nºs primos
PRIMO(n):
	se n<=1, devolva não;
	para i de 2 até n-1, faça:
		se i divide n, devolva não;
		else devolva sim;
-----------------------------------------------------------------------------------------------------
f(n) = O(g(n))  nunca pode ser lido como "igual"

"complexiade é" ou "coplexidade pertence" ou "complexidade pertence ao grupo de funções limitadas assintóticamente por g(n) "

vantagem da notação = : não precisa fazer descrição de cada uma das funções
limite: não se pode fazer 3n²=5n² -> 3=5
-----------------------------------------------------------------------------------------------------
similar/analogamente à notação O, existe a notação omega para limites inferiores

dizemos que f(n) = omega (g(n)) se existe n0 natural e c>0 tais que
	f(n)>= c*g(n) para todo n>=n0
-----------------------------------------------------------------------------------------------------

<< e >> significa ser dominado assintoticamente inferiormente/superiormente

ex:
f(n) << g(n) significa que limite n indo para o infinito de f(n)/g(n)=0

com isso se determina uma hierarquia entre as funções
-----------------------------------------------------------------------------------------------------
limite de n indo para zero de (n^k)/(C^n) =
limite de n indo para zero de ( K * (n^(k-1)))/ ((ln C)* C^n)=
0

ou seja , não importa se C é 1,0000001 e n tende a zero, C^n cresce muito mais rápido que n^k
-----------------------------------------------------------------------------------------------------
n! <= n^n
log n! <= log n^n
n log n <= n^2
n!= 2 ^ (log n!) <= 2^ (n^2)