Jump to content
polska

Complexidade

Recommended Posts

polska

Boas pessoal, queria compreender melhor como classificar a complexidade de problemas, e para isso peguei no problema Cromos Repetidos, da qualificação para as ONI deste ano, e voltei a fazê-lo, como é óbvio e com algumas coisas que aprendi, fiz uma solução muito melhor, mas agora, queria saber a complexidade de cada uma..

Este é o código que fiz á uns meses:

#include <stdio.h>
int main(){
int l,v[100000][2],INF,SUP,conta=0;
scanf("%d",&l);
for(int i=0;i<l;i++){
 scanf("%d %d",&INF,&SUP);
 v[i][0]=INF;
 v[i][1]=SUP;
}
for(int i=0;i<l;i++){
 for(int j=i+1;j<l;j++){
  if(v[i][0]>=v[j][0] && v[i][1]<=v[j][1]){
v[i][0]=1;
v[i][1]=0;
  }
  if(v[i][0]<=v[j][0] && v[i][1]>=v[j][1]){
v[j][0]=1;
v[j][1]=0;
  }
  if(v[i][0]>=v[j][0] && v[i][0]<=v[j][1]){
v[i][0]=v[j][1]+1;
  }
  if(v[i][1]>=v[j][0] && v[i][1]<=v[j][1]){
v[i][1]=v[j][0]-1;
  }
 }
}
for(int i=0;i<l;i++){
 conta=conta+(v[i][1]-v[i][0]+1);
}

printf("%d\n",conta);
return 0;
}

Este foi o que fiz ontem, onde já fiz o sort de elementos e apenas precisei de um for para testar as condições, usei também uma struct para ordenar no merge sort dois elementos de uma so vez, como me foi dito no tópico sorting ;D ..

#include <stdio.h>
#define MAX 100000

typedef struct ex
{
int inf;
int sup;
}CROMOS;

CROMOS intervalos[MAX];
CROMOS B[MAX];

/***********************************************************************************************************************************/
void mergesort( int inicio, int final )
{
int esquerda = 0, direita = 0, meio = 0;
int i = 0;

if( inicio == final )
 return;

meio = ( inicio+final ) / 2;

mergesort( inicio, meio );
mergesort( meio+1, final );

esquerda = inicio;
direita = meio+1;

for( i=inicio; i<=final; i++ )
{
 if( direita > final  || ( esquerda <= meio && intervalos[esquerda].inf <= intervalos[direita].inf ) )
 {
	 B[i] = intervalos[esquerda];
	 esquerda++;
 }
 else
 {
	 B[i] = intervalos[direita];
	 direita++;
 }

}
for( i=inicio; i<=final; i++ )
  intervalos[i] = B[i];
}

/***********************************************************************************************************************************/
int main()
{
int N, resultado;

scanf( "%d", &N );

//intervalos
for( int i=0; i<N; i++ )
{
 scanf( "%d %d", &intervalos[i].inf, &intervalos[i].sup );
}

//sort
mergesort( 0, N-1 );

//default
resultado = intervalos[0].sup;

//calculos
for( int i=1; i<N; i++ )
{
 if( intervalos[i].inf > resultado )
 {
  resultado += ( intervalos[i].sup-intervalos[i].inf ) + 1;
 }
 else if( intervalos[i].sup > resultado )
 {
  resultado += ( intervalos[i].sup-resultado );
 }
}

//resultado
printf( "%d\n", resultado );

return 0;
}

o mege sort aparece com espaços onde não devia e assim, mas não é culpa minha xb

Eu não sei muito bem como classificar, mas tendo em conta o que pesquisei.. Na primeira solução penso que seja O(N^2) , por ter dois loops até N e não fazer a ordenação dos elementos, já no segundo, penso que tenho O(log n) , pois tenho apenas um loop até N, e tenho o sort dos elementos que penso que no pior dos casos é O(n log n) ...

Não sei se estou a dizer grande disparate ou não, mas ajudem-me :D

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
pmg

Não analisei os teus programas, só quero apontar uma coisa:

se tens um sort (por comparação) no teu programa a complexidade nunca é melhor que O (n log n); portanto não pode ser O (log n).


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
Flinger

O ciclo que tens até N é o input dos dados... Nesta questão não conta para a análise da complexidade, visto que o que tu queres calcular é a ordenação.

De qualquer forma, a adição de tempos normalmente não produz alterações no grau de complexidade.

O(N) + O(N) = 2 O(N) = O(N)

no teu caso, O(N) + O(N log N) = O(N log N). Podes considerar como se O(N) fosse desprezável face a O (N log N).

Penso não estar a dizer asneiras... mas nunca se sabe :D

O grau de complexidade do merge sort é O(N log N): http://pt.wikipedia.org/wiki/Merge_sort

Edited by Flinger

Share this post


Link to post
Share on other sites
polska

Não analisei os teus programas, só quero apontar uma coisa:

se tens um sort (por comparação) no teu programa a complexidade nunca é melhor que O (n log n); portanto não pode ser O (log n).

certo :)

O ciclo que tens até N é o input dos dados... Nesta questão não conta para a análise da complexidade, visto que o que tu queres calcular é a ordenação.

De qualquer forma, a adição de tempos normalmente não produz alterações no grau de complexidade.

O(N) + O(N) = 2 O(N) = O(N)

no teu caso, O(N) + O(N log N) = O(N log N). Podes considerar como se O(N) fosse desprezável face a O (N log N).

Penso não estar a dizer asneiras... mas nunca se sabe :D

O grau de complexidade do merge sort é O(N log N): http://pt.wikipedia.org/wiki/Merge_sort

Então no meu programa tenho O( N log N ), isso é muito bom xD


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
mogers

Pode ser O(N log N) mas está errado :/

Falha num exemplo tão simples como

1
2 2

A resposta é 1.

A lógica não tá correcta. Revê isso, n podes usar o resultado nessas comparações nos intervalos


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
polska

Pode ser O(N log N) mas está errado :/

Falha num exemplo tão simples como

1
2 2

A resposta é 1.

A lógica não tá correcta. Revê isso, n podes usar o resultado nessas comparações nos intervalos

Não posso?


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
mogers

outro exemplo

3
1 2
100 110
100 110

O teu resultado dá 24... pensa um pouco melhor...


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
polska

Pois, não posso usar o resulta das condições.. xD

mergesort( 0, N-1 );
resultado = ( intervalos[0].sup-intervalos[0].inf ) + 1;
for( int i=1; i<N; i++ )
{
 if( intervalos[i].inf > intervalos[i-1].sup )
 {
  resultado += ( intervalos[i].sup-intervalos[i].inf ) + 1;
 }
 else if( intervalos[i].sup > intervalos[i-1].sup )
 {
  resultado += ( intervalos[i].sup-resultado );
 }
}
printf( "%d\n", resultado );

Penso estar correcto agora ;D


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
mogers

resultado += ( intervalos[i].sup-resultado );

Isto nunca estará correcto


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
polska

resultado += ( intervalos[i].sup-resultado );

Isto nunca estará correcto

Tendo eu os intervalos ordenados só preciso de testar duas condições, imaginando o caso:

teste:

4

1 6

12 15

6 9

3 8

sort:

1 6

3 8

6 9

12 15

Eu não me preciso de preocupar com o mínimo, pois os intervalos estão ordenados por ordem crescente de intervalo inferior, apenas tenho de actuaizar o resultando consoante o intervalo máximo .

Então só preciso de ver primeiro se tenho um intervalo cujo mínimo é maior que o resultado actual, se tiver , tenho que subtrair esse mesmo intervalo, e adicionar ao resultado... se isto não acontecer, tenho apenas de ver se o máximo do intervalo é maior que o resultado e actualizo...

resultado = ( intervalos[0].sup-intervalos[0].inf ) + 1;

for( int i=1; i<N; i++ )
{
 if( intervalos[i].inf > resultado )
 {
  resultado += ( intervalos[i].sup-intervalos[i].inf ) + 1;
 }
 else if( intervalos[i].sup > resultado )
 {
  resultado = intervalos[i].sup;
 }
}

voltei a modificar..

Atribuo o valor default: (6-1) +1 , resultado = 6

depois entra no loop

1ª iteração: (intervalo -> 3 8 ) , entra na segunda condição, resultado = 8 ;

2ª iteração: (intervalo -> 6 9 ) , entra na segunda condição, resultado = 9 ;

3ª iteração: (intervalo -> 12 15 ), entra na primeira condição, 9 += (15-12)+1 = 13

Não esta bem?

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
mogers

Isso só pode funcionar em alguns casos em que estás a misturar o número de cromos distintos com os seus ids. Experimenta casos em que os intervalos não comecem em 1 e sejam seguidos. Exemplo

2
10 10
10 10

esse código responde 2 em vez de 1.

O core da ideia base já a tens mas simplesmente não podes usar o número de cromos distintos actual (var resultado) na comparação de intervalos, tens simplesmente de comparar os ids que já contabilizaste.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
polska

Isso só pode funcionar em alguns casos em que estás a misturar o número de cromos distintos com os seus ids. Experimenta casos em que os intervalos não comecem em 1 e sejam seguidos. Exemplo

2
10 10
10 10

esse código responde 2 em vez de 1.

O core da ideia base já a tens mas simplesmente não podes usar o número de cromos distintos actual (var resultado) na comparação de intervalos, tens simplesmente de comparar os ids que já contabilizaste.

Certo, já entendi o queres dizer, mesmo assim, como só tenho que me importar com o máximo, tenho de comparar apenas com o intervalo superior dos ids que já contabilizei, para isso, passo a ter uma variavel que contenha o valor superior maior, e depois faço as condições com essa var, e actualizo-a se a condição for verdadeira..

resultado = ( intervalos[0].sup-intervalos[0].inf ) + 1;
supIndex = intervalos[0].sup ;

for( int i=1; i<N; i++ )
{
 if( intervalos[i].inf > supIndex )
 {
  resultado += ( intervalos[i].sup-intervalos[i].inf ) + 1; 
  supIndex = intervalos[i].sup;
 }
 else if( intervalos[i].sup > supIndex )
 {
  resultado = intervalos[i].sup;
  supIndex = intervalos[i].sup;
 }
}


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
mogers

Tá a melhorar, mas com aquilo que ja disse, consegues encontrar facilmente um caso de teste em que esse código ainda falha


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
polska

hum, agora só me ocorre a possibilidade de o primeiro intervalo ser 0 0 ou ter um 0, ai já não tenho certo, tenho de mudar no default:

if( intervalos[0].inf == 0 && intervalos[0].sup == 0 )
 resultado = 0;
else if( intervalos[0].inf == 0 && intervalos[0].sup != 0 )
 resultado = intervalos[0].sup;
else
 resultado = ( intervalos[0].sup-intervalos[0].inf ) + 1;
supIndex = intervalos[0].sup ;


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
mogers

tens de ir desenvolvendo a capacidade de testar os programas, é tão importante em concursos como na vida profissional. Eu penso que a partir daqui é melhor seres tu a arranjar os casos de teste que "breakam" o teu programa.

resultado = intervalos[ i ].sup;

Isto não pode estar certo. Se o input tiver intervalos do tipo 100000 100001 estás a por o resultado a 100001 quando de facto só existiam 2.

O teu código anterior está quase correcto, esta questão sobre o 0 nem se coloca pois no enunciado os cromos são >= 1


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
polska

tens de ir desenvolvendo a capacidade de testar os programas, é tão importante em concursos como na vida profissional. Eu penso que a partir daqui é melhor seres tu a arranjar os casos de teste que "breakam" o teu programa.

resultado = intervalos[ i ].sup;

Isto não pode estar certo. Se o input tiver intervalos do tipo 100000 100001 estás a por o resultado a 100001 quando de facto só existiam 2.

O teu código anterior está quase correcto, esta questão sobre o 0 nem se coloca pois no enunciado os cromos são >= 1

tens razão, eu lembro-me do que pede o problema por isso não fui verificar, mas tens razão, os cromos são >=1 ....

oh, que fail, eu alterei o resultado na primeira condição mas não alterei na segunda, por isso é que nem sequer pensei em mais casos, e só me lembrei dos intervalos com 0's , :confused:

Fica assim:

for( int i=1; i<N; i++ )
   {
       if( intervalos[i].inf > supIndex )
       {
           resultado += ( intervalos[i].sup-intervalos[i].inf ) + 1;  
           supIndex = intervalos[i].sup;
       }
       else if( intervalos[i].sup > supIndex )
       {
           if( intervalos[i].inf == supIndex )
               resultado += ( intervalos[i].sup-intervalos[i].inf )-1;
           else
               resultado += intervalos[i].sup-supIndex;

           supIndex = intervalos[i].sup;
       }
   }

E já passa em casos com intervalos iguais, com intersecções e com intervalos separados..

Ou em casos que tenha tudo junto, tipo:

10

5 20

25 25

25 40

50 60

60 65

63 65

65 150

70 100

80 80

90 151


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
mogers

Tu estás a adicionar ifs ao programa e nem os testas em condições :P

if( intervalos[i].inf == supIndex )
   resultado += ( intervalos[i].sup-intervalos[i].inf )-1;

Esta condição é desnecessária e o problema é que está errada (basta testares com algo como 1 2, 2 3). Esse caso é correctamente calculado com

resultado += intervalos[i].sup-supIndex;

Resumindo, basta-te

resultado = supIndex = 0;

for( int i=0; i<N; i++ )

if( intervalos[i].sup > supIndex ) {

if( intervalos[i].inf > supIndex )

resultado += ( intervalos[i].sup-intervalos[i].inf ) + 1;

else

resultado += intervalos[i].sup-supIndex;

supIndex = intervalos[i].sup;

}

Edited by pmg
converti uma formatacao de codigo em GeSHi

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
polska

Tu estás a adicionar ifs ao programa e nem os testas em condições :P

if( intervalos[i].inf == supIndex )
resultado += ( intervalos[i].sup-intervalos[i].inf )-1;

Esta condição é desnecessária e o problema é que está errada (basta testares com algo como 1 2, 2 3). Esse caso é correctamente calculado com

resultado += intervalos[i].sup-supIndex;

Resumindo, basta-te

resultado = supIndex = 0;

for( int i=0; i<N; i++ )

if( intervalos[i].sup > supIndex ) {

if( intervalos[i].inf > supIndex )

resultado += ( intervalos[i].sup-intervalos[i].inf ) + 1;

else

resultado += intervalos[i].sup-supIndex;

supIndex = intervalos[i].sup;

}

Ai jesus, isso é o dobro da simplificação XD ...

Eu estava tão entusiasmado por ter conseguido reduzir a complexidade do primeiro programa para este que depois quando disseste que estava errado acabei por tentar "arranjá-lo" á força, mas era simples :D ..

Thanks :D


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.