hej behöver hjälp med tidskomplexitet!!!

2013-05-27, 13:14 #1

Medlem

Reg: Dec 2010

Inlägg: 53

Hej! jag vill bara se om jag har förståt tidkomplexitet rätt, jag ar ingen facit på frågorna så jag änkte räta mig här

Kod:

for( int i=1; i<2n; i++)
x=x+1;

Den är o(N)

Kod:

a2) 
for( int i=1;i<n*n; i++)
x=x+1;
for(int j=1;j<n; j++)
x=x+3;

O(N^2)

Kod:

a3)
 for(int i=n;i>0;i=i/2)
x=x+1;
}

O(logN)

Kod:

a4) 
i=n;
while(i>=1){
for( int j=1;j<n;j++)
x=x+1;
i=i/2;
}
b)

O(NlogN)

har jag rätt?

Citera

2013-05-27, 13:25 #2

Medlem

Reg: Nov 2008

Inlägg: 838

Citat:

Ursprungligen postat av agneos

Kod:

a2) 
for( int i=1;i<n*n; i++)
x=x+1;
for(int j=1;j<n; j++)
x=x+3;

O(N^2)

Det är lite oklart hur du menar att looparna nästlar sig (är det ren Java så är de förstås ej nästlade, men det känns som att det likaväl kan vara pseudokod du talar om).

Kod:

for (int i=1;i<n*n; i++) {
  x=x+1;
}
for (int j=1;j<n; j++) {
  x=x+3;
}

I detta fall är komplexiteten O(n^2+n)=O(n^2)

Om du däremot menar att j-loopen ligger inuti i-loopen på följande sätt:

Kod:

for (int i=1;i<n*n; i++) {
  x=x+1;
  for (int j=1;j<n; j++) {
    x=x+3;
  }
}

gäller komplexiteten O(n^2*n)=O(n^3)

Två andra exempel som ger O(n^2) är:

Kod:

for (int i=1;i<n; i++) {
  x=x+1;
  for (int j=1;j<n; j++) {
    x=x+3;
  }
}

och

Kod:

for (int i=1;i<n*n; i++) {
  x=x+1;
}

För övrigt råder jag dig starkt att hålla dig till nollindexering i dina loopvariabler, även om detta är en smaksak

__________________
Senast redigerad av Uber0n 2013-05-27 kl. 13:32.

Citera

2013-05-27, 13:33 #3

Medlem

Reg: Dec 2010

Inlägg: 53

Det här en tenta som jag tränar på

Citera

2013-06-11, 12:13 #4

Medlem

Reg: Nov 2008

Inlägg: 838

Citat:

Ursprungligen postat av agneos

Det här en tenta som jag tränar på

Fick du kläm på det till slut? Jag hoppas att tentan gick bra för dig

Citera

hej behöver hjälp med tidskomplexitet!!!

Skapa ett konto eller logga in för att kommentera

Skapa ett konto

Logga in