analise de complexidade algoritmos

CyberOps

I'm cool cuz I Fold
Boas,

tenho aqui este codigo e estou com algumas duvidas em achas a complexidade disto

Código:
for(int i=0; i<sequencia.length; i++){
	for(int j=i; j<sequencia.length; j++){
		soma=0;
		for(int z=i; z<j; z++)
			soma=soma+sequencia[z];
				
		if(soma==valor)
			return qq coisa					
				
	}
}

ora ainda consigo achar parte:

1 (atribuicaoa do i) + 2n (duas atribuicoes do i++ e j=i n vezes) + (3((n)+(n-1)+(n-2)... (j++, soma=0 e z=i. isto tem q se transformar num somatorio mas n estou a ver como) etc etc)

depois aquele terceiro ciclo for também está a complicar. alguem me consegue ajudar pff?
 
Última edição:
acho q ja fiquei a perceber a logica disto. pelo menos com chegar aos sumatorios mas depois desfaze-los...

outra cena q me intriga é q tu contas as comparaçoes dos ciclos for's para a complexidade e curiosamente o prof da cadeira nao. claro q isso influencia.

onde tens sumatorio k4, o k4 salta fora pq não está a variar em z certo? mas depois como é q chegaste a (j-1+i+1)? existe algum site com "regras" para trabalhar com os sumatorios onde me possa guiar?

muito obrigado pela ajuda, daqui a pouco ja meto mais outros for's com a respectiva analise para ver se entendi.

ja agora fica aqui 1 exemplo q ele tem nos acetatos.
imgqq9.png
 
Última edição:
ja agora, quando tens um somatorio do tipo 'sum (j=1 até n) i' isto vai ser igual a 'i'? ou o i salta para fora e fica 'i*sum(j=1 até n) 1'
 
entao quer dizer que

sum (j=1 até n) i != i * sum (j=1 até n) 1

O i só passa para fora do somatório se for uma constante.

sum (j=1 até n) i = (n*(n+1)/2)

Repara lá na regra. Isso seria assim se, no somatório, a variável que era incrementada era o i, mas nesse caso é o j, logo não se pode fazer assim.
sum (j=1 até n) i = n*i porque j != i, logo os diferentes valores de j não vão influenciar i, logo esse somatório resume-se a fazer n vezes a soma de i.
 
O i só passa para fora do somatório se for uma constante.



Repara lá na regra. Isso seria assim se, no somatório, a variável que era incrementada era o i, mas nesse caso é o j, logo não se pode fazer assim.
sum (j=1 até n) i = n*i porque j != i, logo os diferentes valores de j não vão influenciar i, logo esse somatório resume-se a fazer n vezes a soma de i.

ah, fixe. agora fiquei esclarecido. muito obrigado + uma vez :)
 
basicamente tenho diversos algoritmos e tenho q achar a complexidade deles e relacionar com os tempos de execução. este so tem 2 ciclos for. a complexidade deste tb é quadratica? é q pela a analise dos tempos este é mais eficiente pelo q me parece q este nao pode ser quadrática também.
 
Back
Topo