1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

analise de complexidade algoritmos

Discussão em 'Programação' iniciada por CyberOps, 23 de Fevereiro de 2008. (Respostas: 31; Visualizações: 2412)

  1. CyberOps

    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: 23 de Fevereiro de 2008
  2. Baderous

    Baderous Banido

    Fica aqui a resolução feita por mim:

    [​IMG]
     
  3. CyberOps

    CyberOps I'm cool cuz I Fold

    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.
    [​IMG]
     
    Última edição: 23 de Fevereiro de 2008
  4. Baderous

    Baderous Banido

    Estão aqui as regras que utilizo nestes exercícios:

    [​IMG]
     
  5. CyberOps

    CyberOps I'm cool cuz I Fold

    mas n explicas ai como é q sum (z=i ate j-1) 1 = j-1-i+1
     
  6. Baderous

    Baderous Banido

    1ª regra.
     
  7. CyberOps

    CyberOps I'm cool cuz I Fold

    ya, acho q ja estou a perceber. consideras sum (i=a ate b) 1 =b-a+1. deves ter esquecido do 1 e do igual nao?
     
  8. Baderous

    Baderous Banido

    Ya.
     
  9. CyberOps

    CyberOps I'm cool cuz I Fold

    muito obrigado :). ja agora, andas na univ do minho deves conhecer o prof Rui José, nao? veio dar uma palestra a coimbra sobre sistemas ubiquos e propor uns projectos para a disciplina. mto porreiro o prof
     
  10. Baderous

    Baderous Banido

    Por acaso não. Mas eles também são tantos...
     
  11. CyberOps

    CyberOps I'm cool cuz I Fold

    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'
     
  12. Baderous

    Baderous Banido

    Usas a 2ª regra de baixo. Consideras é que o somatório é de j=0 até n-1 (para ficar como na fórmula).
     
  13. CyberOps

    CyberOps I'm cool cuz I Fold

    sim, mas a variavel dentro do somatorio nao é j, mas sim i. logo o somatorio nao varia, ne?
     
  14. Baderous

    Baderous Banido

    Sim. Mas penso que essa situação nunca ocorre.
     
  15. CyberOps

    CyberOps I'm cool cuz I Fold

    entao quer dizer que

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

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

    Baderous Banido

    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.
     
  17. CyberOps

    CyberOps I'm cool cuz I Fold

    ah, fixe. agora fiquei esclarecido. muito obrigado + uma vez :)
     
  18. CyberOps

    CyberOps I'm cool cuz I Fold

    vê se este está correcto sff

    [​IMG]
     
  19. Baderous

    Baderous Banido

    Voltaste a fazer o que eu já tinha feito.
     
  20. CyberOps

    CyberOps I'm cool cuz I Fold

    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.
     

Partilhar esta Página