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

Complexidade

Discussão em 'Programação' iniciada por Biker_, 24 de Maio de 2006. (Respostas: 9; Visualizações: 833)

  1. Biker_

    Biker_ Power Member

    Alguém percebe de classes de complexidade? Aquela cena do O (ó grande)?

    Estou super esquecido disso e pelos apontamentos que tive a ler não fiquei mto esclarecido.

    Por exemplo, qual a complexidade do seguinte exemplo?

    Código:
    void xpto(x) {
       if(x == 0) {
          for(i=0;i < n.length;i++) {
             ...
          }
    
          for(i=0;i < n.length;i++) {
             ...
          }
       }
    
       for(i=0;i < n.length-1;i++) {
          x = ...
          xpto(x);
       }
    
    }
     
    Última edição: 24 de Maio de 2006
  2. ScOrpion-boy

    ScOrpion-boy Banido

    Pelo que sei esse exemplo é de O(n)=1, pois não tens nenhum if dentro de outro. Ou seja a sua complexidade temporal é linear.
     
  3. Jorge Candeias

    Jorge Candeias Power Member

    Nepia ele no último for tem ali uma recorrência, mas tambem nunca percebi muito disso


    Cumprimentos
     
  4. Biker_

    Biker_ Power Member

    Alterei uma coisita, para verem que há paragem nisto. :lol:

    Então e a recursividade dentro do for? De certeza que há-de fazer mossa...
     
  5. Sadino

    Sadino I'm cool cuz I Fold

    Experimenta ir aqui :)
     
  6. ScOrpion-boy

    ScOrpion-boy Banido

    Não tinha reparado :lol:

    Sendo assim axo que é de ordem n^2. Pois é como se tivesses dois ciclos for dentro de 1. Mas não tenho a certeza!! esse if(x==0 ) :wow:
     
  7. HecKel

    HecKel The WORM

    n^2 seria no caso de teres um for dentro de outro for, no teu caso tens NO PIOR CASO O(n)+O(n)+O(n) = 3*O(n) => O(n) e no MELHOR CASO (quando n entras no IF) O(n) apenas

    O "O(n)" significa "complexidade de ORDEM n".

    Vê o link que o Sadino postou :)

    abraços, HecKel
     
  8. Biker_

    Biker_ Power Member

    Mas a recursividade não faz pesar mais o último "for" do que apenas O(n)? Tenho a impressão que sim, mas não sei qual a sua complexidade... não consegui perceber pelo que li nos apontamentos que tenho.

    Já tinha visto o link, mas acho que não tem "nada de novo" que me me possa ajudar... :sad:
     
  9. HecKel

    HecKel The WORM

    nem tinha reparado nesse detalhe... :O

    recursividade vai dar algo similar a exponencial...

    Tendo em conta que esse for vai chamar N vezes xpto(x) que por sua vez executa esse for...., vai ser algo uma beca abusado, algo do tipo n^n, mas já agora, o que é aquele "n" que aparece em n.lenght? Isso pode determinar melhor a complexidade..., tal como dá jeito saber que valor o x vai obter para saber quando e se entra dentro do if :)

    Faltam alguns dados para analizar com maior exactidão, mas só a recursividade aumenta drásticamente a complexidade...

    abraços, HecKel
     
  10. Biker_

    Biker_ Power Member

    O "n.lenght" na verdade foi para exprimir melhor o tamanho da coisa. Aquilo vai ter n elementos e para cada elemento vai ter de percorrer a função "xpto". Dp cada elemento está interligado aos outros, logo quando se faz algo a um elemento é preciso fazer algumas verificações nos outros, daí os "for".
    Ele entra no "if" quando o valor de "X" é 0. Ou seja, na verdade só vai entrar no if "n" vezes durante a aplicação, já que dp o 0 é alterado para outro valor. Mas pronto, isso são pormenores de implementação que não afectam a estrutura do programa e como tal não vão afectar a sua complexidade.
     

Partilhar esta Página