För vilka k är O(n+k) och O(n+k*logk) linjära?
Jag har problem med hur jag ska resonera kring tidskomplexitet för denna fråga. Det finns redan en tråd om denna uppgift som jag hittade men finns tyvärr inget svar där så jag testar att fråga igen själv.
https://www.pluggakuten.se/trad/sorteringsalgoritm-med-tidskomplexitet-o-n-k-log-k/
Det ena fallet är counting sort där input är en lista med n st heltal där alla är mellan 0 och k d.v.s k=största elementet i listan, denna har komplexitet O(n+k). Hur ska man hitta ett samband mellan n och k här när k inte har något att göra med n? Om man behandlar k som en konstant får man väl linjär tid för alla k när n växer?
Det andra fallet är en alternativ sorteringsalgoritm där n fortfarande är antalet element (heltal) i listan men k är istället antalet unika tal, denna har komplexitet O(n+k*logk). Här kan man i alla fall dra slutsatsen att k<=n eftersom det som max kan finnas n st olika heltal i listan med n element. Om k då skulle vara lika med n är O(n+k*logk)=O(n+n*logn) som uppenbart inte är O(n). Var går då gränsen för när k*logk är O(n)?
Skulle uppskatta all hjälp med att resonera kring detta, tack på förhand.
O(n+k) är linjärt i både n och k.
I det andra fallet kan vi betrakta två extremfall:
1) alla tal är olika. Då är k = n och vi har O(nlogn)
2) det finns bara två olika värden (k = 2). Då har vi O(n+2) och det är samma som O(n).
Om k är ett konstant antal, så har vi O(n). Om k är proportionell mot n så har vi O(nlogn).
Gränsen som du söker får man om klogk är ungefär lika med n. Jag tror inte k som funktion av n har något namn i det fallet, men vi kan se några värden:
n k så att klogk = n
100 30
1000 200
10000 1500
Om k är ett konstant antal, så har vi O(n). Om k är proportionell mot n så har vi O(nlogn).
Denna del verkar helt rimlig men jag har svårt att förstå hur man ska avgöra det. k i detta fall beror helt på listan men är inte nödvämdigtvis proportionell mot listans storlek n. Känns som att det finns lite väl många fall att tänka på.
Om k är konstant d.v.s om vi tänker ex. endast siffrorna 0-9 kommer tiden självklart bli linjär även om n är stort p.g.a upprepningar. Om man däremot bara skapar listor med slumptal kan väl ex. listan [1,10000000] ta längre tid att sortera än en lista med 100 siffror där alla är mellan ex. 0 och 9.
Hur skulle du tolka frågan? Får man tolka k som en konstant trots att den beror på input (men inte ditekt på n)?
Vad är själva frågan?
Implementera, dokumentera och testa en algoritm som sorterar heltalen x1, x2, ..., xn. För samtliga tal xi gäller att 0 ≤ xi ≤ k. Din algoritm ska ha värstafallstidskomplexitet O(n+k). För vilka värden på k blir algoritmen linjär?
Designa en algoritm som som sorterar n stycken heltal där det förekommer upprepningar. Det totala antalet olika tal är k. Beskriv algoritmen i pseudokod. Din algoritm ska ha tidskomplexitet O(n + klog(k)). Förväntad tid räcker. För vilka värden på k blir algoritmen linjär?
Jag har fixat båda algoritmerna men enda problemet är slutfrågan i båda.
För alla värden på k, i betydelsen att k är en konstant, blir algoritmen linjär. Frågan är konstig. Om k är en funktion av n, så kan slutresultatet bli O(n) eller O(nlogn). (Eller nånting emellan, t.ex. O(nlognlogn).
Tycker också den är konstig, får väl tolka det som att k är konstant och anta att båda är linjära för alla k även om det inte känns som målet med frågorna.
