Stor O-notasjon java

[Sher]

Hei!

Noen som vet hva O-notasjon er? Hvordan kan man regene ut tidforbruket til et program?

 

f.eks Følgende programbit vil sortere en heltallsarray int[] A= new int [n]. Av hvilken orden orden er tidsforbruket til dette programmet?

 

for (int i =0; i<n; i++){

minj=i;

for(j = i+j; j< n; j++) {

if (A[j] <A[minj]){

minj = j;

}

}

bytt(i, minj);

}

 

Er det noen som kan hjelpe meg i å forstå det her???

[sven-o]

Hei!

Noen som  vet hva O-notasjon er? Hvordan kan man regene ut tidforbruket til et program?

...

...

Er det noen som kan hjelpe meg i å forstå det  her???

"Stor O" notasjon brukes til å vise kompleksiteten til en algoritme, f.eks en sorteringsalgoritme.

Den viser ikke tiden det vil ta, men hvor mange operasjoner(i ditt tilfelle funksjonen bytt()) algoritmen trenger for å fullføre en oppgave ved et worst-case scenario.

 

Kompleksiteten til programmet ditt kan du regne ut selv. Regner med at dette er en skoleoppgave.

[Sher]

Hei igjen!

 

Takk for at du svarte Sven-o Du har rett i at det er en skole oppgave, men det er en gammel oppgave og svaret på den er "O(n^2)". Men det jeg lurer på er hvordan man kommer fram til svaret? hva må man regne ut og hvordan?

[anderlin]

Algoritmen går igjennom tabellen fra element 0 til n, og bytter det minste elementet med det første. For å finne det minste må den søke gjennom hele. Så ser den på tabellen fra 1 til n og gjør det samme. Så 2 til n og opp til det ikke er flere elementer.

 

Altså blir antallet operasjoner:

 

n + (n-1) + (n-2) + ... + (n-n)

 

Siden O-notasjon bare angir en øvre grense, er det riktig å si at algoritmen er O(n^2).

I theta-notasjon ville det blitt n^2 - (n^2 + n)/2

 

Hvis man bare regnet bytt-funksjonen, ville algoritmen sortert i lineær tid. Er ikke så veldig stødig på dette, så hva er riktig? Telles ikke sammenligninger?

 

EDIT: Fjernet litt mellomregning...

Endret 7. september 2004 av anderlin