Complexidade

[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 😄

Edited July 5, 2012 at 11:54 AM by polska

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

[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 😄

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

Edited July 5, 2012 at 02:43 PM by Flinger

[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 😄

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

[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

[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?

[mogers]

outro exemplo

3
1 2
100 110
100 110

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

[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

[mogers]

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

Isto nunca estará correcto

[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 July 6, 2012 at 06:56 PM by polska

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

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

[mogers]

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

[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 ;

[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

[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 , 😕

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

[mogers]

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

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 July 8, 2012 at 10:20 PM by pmg
converti uma formatacao de codigo em GeSHi

[polska]

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

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

Thanks 😄