Algoritm-uppgift

Hej!

Jag skulle behöva lite hjälp med b) uppgiften här: http://puu.sh/jXOs3/4637985081.png. Vet inte riktigt hur man ska tänka här riktigt, ska man bara kolla det värsta fallet? Men är inte helt med på hur man gör det och hur man ska svara på sådana här uppgifter(är lite oklart i facit).

De där sista två looperna är för i -> n och 1 -> i. Alltså får de tillsammans komplexiteten n. Tar du hänsyn till if loopen så körs de looperna bara varannan gång, alltså n/2. Sedan har ju den första loopen komplexiteten n. Eftersom de är nästlade i varandra (loop i loop) så multiplicerar du n/2 * n = 0,5n^2, vilket med ordo-notation blir O(n^2).

Alright tack för svar men varför får de sista två looperna komplexiteten n tillsammans? Varför väljer man n, är det flest antal gånger(dvs det värsta) som de kan köras och därför väljer man ett n för varje for-loop?

Sen körs väl båda for-looparna om if-satsen stämmer, för finns ju ingen else och de ser ju ut som båda for-looparna ligger under if villkoret.

Om du byter plats på looparna ser du att första går mellan 1 och i, och andra mellan i och n. Totalt går du alltså n+1 steg, där 1an kommer från att du använder i två gånger. Om vi antar att vi kan tilldela i O(1) så får du total tid O(1*(n+1))=O(n) för innersta looparna.

If-satsen kan verifieras i O(1) genom att kolla sista biten (1-udda, 0-jämn), så vi får att if-satsen och looparna tillsammans är O(1) om i-jämn, O(n) om i-udda. Eftersom hälften av alla tal i 1..n är udda får vi alltså n*(O(1)+O(n))/2 operationer. O(1)+O(n)=O(n), O(n)/2=O(n) och n*O(n)=O(n^2). Hela algoritmen är alltså i O(n^2).

Okej men är inte med på vart O(1) kommer ifrån och gäller den här: O(1*(n+1))=O(n) för if-satserna bara eller?

Ena O(1) kommer från antagandet att tilldelning går på konstant tid respektive att man, för att avgöra om ett tal är udda eller jämnt, bara behöver kolla på sista siffran.

O(1*(n+1)) motsvarar att man gör tilldelning n+1 gånger. Förenklar man detta får man O(n+1) vilket är i O(n) eftersom n är det enda signifikanta för stora n.

Okej men som på a)-uppgiften där de skrivit O(1), så tänker man sig att man har O(1) för varje tilldelning, i detta fall en O(1) för x<- x+1 och en O(1) för y<-y+1 ? Är inte med på hur O(1) är med för att avgöra om ett tal är udda eller jämnt. Vi har bara en if-sats för att kolla om den är udda, vi har inget för jämnt liksom. Eller tänker jag helt fel?

I a specificerar de inte vad som görs, bara hur lång tid det tar. För våra ändamål spelar det ingen roll vad som händer. Vi kan däremot inte per automatik utgå från att tilldelningen i b) är i O(1) bara för att det fanns en omärkt komponent i a) som tog O(1). O(1)-operationen i a kan ha varit något helt annat.

Beräkningsmaskinen utför ju ett arbete när den undersöker talet som i det här fallet är O(1) eftersom man bara behöver titta på sista siffran och se om den är udda. Man kan inte per automatik bortse från att det tar beräkningar att evaluera predikat i if-else-satser. Till exempel kunde det stått typ:
vilket tar längre tid än O(1)

Okej men är inte helt med på vad O(1) betyder, tror det är det jag inte greppar. Vad innebär det att tidskomplexiteten för något är O(1)? För du skrev att "O(1*(n+1)) motsvarar att man gör tilldelning n+1 gånger." så man lägger till O(1) när man gör något inuti en loop, i detta fall lägger vi till O(1) för vi har: x<-x+1 och y<-y+1?

Rent formellt säger man att f(x)=O(g(x)) när x går mot oändligheten omm det finns en konstant c så att beloppet av f(x) är mindre än c gånger beloppet av g(x) för alla x större än något visst X.

Att f(x)=O(1) betyder alltså att för tillräckligt stora x beter sig f(x) som en konstant. Att tidskomplexiteten för någon operation är O(1) betyder alltså att det tar konstant tid att genomföra operationen, oavsett vad man utför det på.

Jag tycker att du ska gå tillbaka till din kursbok och öva på begreppet. Har du inte hajat intuitivt vad det är för något så är det omöjligt att svara på uppgifterna med säkerhet.

Okej men då tror jag att jag är med. Kan du kolla om detta tänk är rätt?

Först börjar man inifrån och ser att vi har två loopar som går n+1 steg totalt. Sen antar vi att det tar konstant tid att utföra sakerna inuti de två inersta for-looparna så vi tilldelar O(1) till det så blir den total tiden för de två innersta looparna: O(1*(n+1)) = O(n+1) = O(n) eftersom man multiplicerar den tid man har för en loop med tiden för den andra loopen liksom.

Sen har vi en for-loop i början och tiden för ett for-loopshuvud kan max bli en. Sen eftersom vi har en if-sats som kollar om i är udda och hälften av alla tal är udda kommer vi få dela totala tiden med två eftersom vi inte kör någon else-sats och kollar de jämna talen. Så den totala tiden blir n*(O(n))/2 = O(n^2) där konstanten försvinner då vi inte tar hänsyn till dem.

Det är svårt att bedöma huruvida du förstått eller inte eftersom du fått lösningen serverad.