analise de complexidade algoritmos

CyberOps disse:
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.
Clicar para expandir...

A complexidade neste caso é dada pelo grau do polinómio resultante, logo é quadrática. Isso de parecer não quer dizer nada.
 
Tens uma forma relativamente simples de ver as complexidades.

ciclos (for; while; etc) são de complexidade n, todas as outras operações são de complexidade 1, logo desprezáveis.

ciclos dentro de ciclos equivale a ao produto da complexidade dos mesmos, eg. O(n) * O(n).
ciclos não contidos são do tipo O(n) + O(n) = 2 O(n) = O(n).

No entanto é bom que percebas ou decores algumas operações/algoritmos com complexidades especiais (pesquisas em árvores, os *sort, etc).
 
TuxBoss disse:
Tens uma forma relativamente simples de ver as complexidades.

ciclos (for; while; etc) são de complexidade n, todas as outras operações são de complexidade 1, logo desprezáveis.

ciclos dentro de ciclos equivale a ao produto da complexidade dos mesmos, eg. O(n) * O(n).
ciclos não contidos são do tipo O(n) + O(n) = 2 O(n) = O(n).

No entanto é bom que percebas ou decores algumas operações/algoritmos com complexidades especiais (pesquisas em árvores, os *sort, etc).
Clicar para expandir...

Eu não "desprezaria" todas as operações de complexidade 1.. nem assumiria que tudo o que é ciclo tem complexidade N..

Código: 
[LEFT][FONT=NimbusMonL-Regu][SIZE=1]int count = 0;[/SIZE][/FONT]
[SIZE=1][FONT=NimbusMonL-Regu]int i=1;[/FONT][/SIZE]
[SIZE=1][FONT=NimbusMonL-Regu]while(i<=n)[/FONT][/SIZE]
[SIZE=1][FONT=NimbusMonL-Regu]{[/FONT][/SIZE]
[SIZE=1][FONT=NimbusMonL-Regu]i*=2;[/FONT][/SIZE]
[SIZE=1][FONT=NimbusMonL-Regu]for (int j=1; j<=n; j++)[/FONT][/SIZE]
[SIZE=1][FONT=NimbusMonL-Regu]count++;[/FONT][/SIZE]
[SIZE=1][FONT=NimbusMonL-Regu]}[/FONT][/SIZE][/LEFT]
 
entao qual seria a complexidade desse codigo?

está ali o ciclo for q tem complexidade n. o ciclo while nao tem complexidade n/2?

logo tambem é complexidade quadratica nao? O(n/2 * n) = O( (n^2)/2) = n^2

doginthefog disse:
Eu não "desprezaria" todas as operações de complexidade 1.. nem assumiria que tudo o que é ciclo tem complexidade n.

Código: 
[LEFT][FONT=NimbusMonL-Regu][SIZE=1]int count = 0;[/SIZE][/FONT]
[SIZE=1][FONT=NimbusMonL-Regu]int i=1;[/FONT][/SIZE]
[SIZE=1][FONT=NimbusMonL-Regu]while(i<=n)[/FONT][/SIZE]
[SIZE=1][FONT=NimbusMonL-Regu]{[/FONT][/SIZE]
[SIZE=1][FONT=NimbusMonL-Regu]i*=2;[/FONT][/SIZE]
[SIZE=1][FONT=NimbusMonL-Regu]for (int j=1; j<=n; j++)[/FONT][/SIZE]
[SIZE=1][FONT=NimbusMonL-Regu]count++;[/FONT][/SIZE]
[SIZE=1][FONT=NimbusMonL-Regu]}[/FONT][/SIZE][/LEFT]
Clicar para expandir...
 
CyberOps disse:
exacto. tens razao

Baderous, tens a certeza q o codigo q mostrei no primeiro post e q resolveste é quadratica. cada vez mais acho q é cubica.
Clicar para expandir...

E já agora podes explicar porquê?
Achas que é porque sim?
É que, a não ser que tenhas um método melhor que o meu, isso de "achar" não te leva a lado nenhum (nem mesmo olhando para os tempos de execução...).
 
Baderous disse:
E já agora podes explicar porquê?
Achas que é porque sim?
É que, a não ser que tenhas um método melhor que o meu, isso de "achar" não te leva a lado nenhum (nem mesmo olhando para os tempos de execução...).
Clicar para expandir...

mais por este exemplo dos acetatos do meu prof muito semelhante ao q pus no 1º post

semttulolo4.jpg


o problema é q n sei la chegar lol
 
Última edição:
TuxBoss disse:
Tens uma forma relativamente simples de ver as complexidades.

ciclos (for; while; etc) são de complexidade n, todas as outras operações são de complexidade 1, logo desprezáveis.

ciclos dentro de ciclos equivale a ao produto da complexidade dos mesmos, eg. O(n) * O(n).
ciclos não contidos são do tipo O(n) + O(n) = 2 O(n) = O(n).

No entanto é bom que percebas ou decores algumas operações/algoritmos com complexidades especiais (pesquisas em árvores, os *sort, etc).
Clicar para expandir...

Isso é uma forma demasiado simplista de ver as coisas, e que não se aplica a todos os casos...

-------------------------

Considerando S(i=0,n,i) como sendo o somatório para i de 0 até i, deduzi o seguinte (ignorando as constantes nas partes onde há blocos de complexidade maior, e considerando constantes equivalentes a 1):

S(i=0, n-1, S(j=i, n-1, S(k=i, j-1, 1) ) )
<=> S(i=0, n-1, S(j=i, n-1, j-i ) )
<=> S(i=0, n-1, (n - i) (n - i - 1) / 2 )
<=> S(i=0, n-1, i (i+1) / 2)
<=> S(i=0, n-1, (i^2 + i) / 2)
<=> 1/2 ( S(i=0, n-1, i^2) + S(i=0, n-1, i) )

que tem complexidade igual a:
S(i=0,n-1,i^2)

Ora isto não me parece O(n^2).
Conseguimos sempre ter um valor de n para o qual S(i=0, n-1, i^2) > M * n^2
 
Última edição:
ja agora, no codigo abaixo, pelo debug dá para saber a partida que a complexidade é linear, mas como é q poderia chegar a essa conclusao sem ser desta forma

Código: 
soma=0;
i=0;
j=0;
while(soma!=valor && i<sequencia.length){
	while(soma<valor && j<sequencia.length){
		soma = soma+sequencia[j];
		if(soma==valor)
			return …;
		j=j+1;
	}
soma = soma-sequencia[i];
	i=i+1;
}
 
a complexidade desse algoritmo é n^3

Vejo ai 3 for, logo quem olhe para ai devia suspeitar do mesmo. A analise da complexidade é sobre o que acontece no pior caso.

Se alguém quiser uns pdfs sobre isso que mande PM
 
Última edição:
Inicie sessão ou registe-se para poder participar.
Back
Topo