analise de complexidade algoritmos

[cyberops]

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?

[djthyrax]

Pegando na tua análise,

Para a parte do n + n-1 + n-2: http://www.jimloy.com/algebra/gauss.htm

3(n+(n*(n-1)/2)) = 3((n/2)*(n+1)) = 3(n/2) * 3(n+1) = 3n/2 + 3n+3

Substituindo ali em cima (no teu post),

1 + 2n + 3n/2+3n+3 = 4+3n/2+5n = 4 + (3/2)n+5n = (13/2)n + 4

Mas não te fies naquilo que eu digo. 🙂

[MX+]

Isso é simples:

   n^2 (primeira e segunda iteração
+ n (n + 1) / 2

Mas linearmente é: n^3

[Warrior]

Provavelmente querias colocar um * no início da segunda linha MX+

[MX+]

Provavelmente querias colocar um * no início da segunda linha MX+

Certissimo. Obrigado  🙂