Complexidade

[Biker_]

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?

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);
   }

}

 

[ScOrpion-boy]

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.

 

[Jorge Candeias]

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


Cumprimentos

 

[Biker_]

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

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.

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

 

[Sadino]

Experimenta ir aqui

 

[ScOrpion-boy]

Não tinha reparado

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 )

 

[HecKel]

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

 

[Biker_]

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

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

 

[HecKel]

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

 

[Biker_]

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

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.