«Din venn Lurvik har funnet opp en algoritme. Algoritmen hans kan ta inn en sekvens av lengde \(n\), der \(n\) er et multiplum av \(k\), og sortere den i \(k\) segmenter av lik lengde, slik at elementene i et gitt segment ikke nødvendigvis er sortert seg imellom, men alle elementer i ethvert segment er større enn eller like store som elementene i alle segmenter til venstre, og mindre eller like elementene i alle segmenter til høyre. Gi en nedre grense for kjøretiden til algoritmen. Forklar kort.»

Er det mulig å få en mer detaljert forklaring (enn LF) på hvordan man finner kjøretiden her?

Basert på Piazza-spørsmål fra 2015

Hovedpoenget er å vise at algoritmen kan brukes til å sortere, og så bruke den nedre grensen som gjelder for alle sorteringsalgoritmer. Man kan bruke den til å sortere \(k\) verdier, som gir den nedre grensen \(\Omega(k\log k)\). I tillegg kan man måtte flytte på alle de \(n\) elementene, som gir grensen \(\Omega(n)\).

Vil bare si at jeg kommer heller ikke helt overens med denne oppgaven.

Problemet er å finne kjøretiden på å partisjonere \(n\) elementer inn i \(k\) blokker av lik lengde, der hvert element i en blokk er mindre eller lik hvert element i blokken til høyre.

Intuitivt så tenkte jeg at man først finner summen av alle elementene i listen. Deretter deler man summen på \(k\) for å kunne finne omtrentlig verdi-intervall for hver av de k segmentene. På denne måten kan man grovsortere i lineær tid hvilket segment hvert element burde tilhøre, og deretter kan man muligens finjustere i lineær tid slik at alle de \(k\) segmentene får identisk lengde. Dette vil kanskje funke.

Oppgaven er å bevise at det du prøver å gjøre er umulig. For å ta et enkelt tilfelle: La oss si at algoritmen din er rett. Da kan jeg bruke den med \(k=n\) til å sortere vilkårlige elementer i lineær tid, noe som beviselig er umulig. Ergo kan ikke algoritmen din stemme.

Men, sier du kanskje, hva med \(k<n\)? La oss si at \(k=n/3\), og at den er låst fast? OK, kanskje sekvensen min er \(a_1,a_2,\dots,a_m\). Jeg kan da i lineær tid konstruere sekvensen \(a_1,a_1,a_1,a_2,a_2,a_2,\dots,a_m,a_m,a_m\). Denne sekvensen har lengde \(n=3m\). Du mener altså at algoritmen din kan løse problemet i oppgaven på denne sekvensen i lineær tid – som også vil være lineært som funksjon av \(m\) (dvs., ikke bare av \(3m\)). La oss si at svaret er \(b_1, b_2, \dots, b_{3m}\). Da kan jeg velge meg \(b_1, b_4, b_7, \dots, b_{3m-2}\) som løsning, og dermed ha en sortert versjon av min opprinnelige sekvens. I lineær tid. Og det er umulig.

Med andre ord: Algoritmen din kan ikke la meg få ut denne løsningen med en kjøretid som er bedre enn \(\Omega(m\log m)\) i verste tilfelle. (I det mer generelle tilfellet kan jeg altså bruke algoritmen til å sortere \(k\) elementer.)

Jeg vet ikke om det klargjør ting på noe vis. Jeg skjønte jo muligens ikke helt hva du lurte på i utgangspunktet, så … du får bare stille flere spørsmål, om nødvendig :)

Hva er poenget med å replikere dem? Hva gjør en så med de replikerte enhetene?

Du gjør ingenting med dem. Du skal bare lage gyldig input til Lurviks algoritme. Når han er ferdig vil de replikerte elementene ligge ved siden av hverandre, og du kan bare plukke ut ett element fra hvert segment, som forklart i svaret over.

Jeg forstår ikke helt hvordan du kommer frem til henholdsvis \(\Omega(k\log k)\) og \(\Omega(n)\). For \(\Omega(k\log k)\) tolker jeg det som at du bruker argumentet at den nedre grensen for sorteringsalgoritmer er \(\Omega(n\log n)\), men jeg forstår ikke helt hvordan dette relateres til segmentene \(k\). La oss ta et trivielt eksempel og si at du har en sekvens med tall gitt som \(\langle 3, 4, 1, 2, 6, 5, 9, 8, 7\rangle\), og \(k = \frac{n}{3}\) hvor \(n = 9\) i dette tilfellet. Algoritmen vil da dele denne sekvensen opp i \(3\) segmenter med fast lengde \(3\), der hver segment inneholder elementer som er mindre eller lik segmentet til høyre etc. Altså, algoritmen kan gi følgende \(\langle 3, 1, 2\rangle\), \(\langle 4, 6, 5\rangle\), \(\langle 9, 8, 7\rangle\). Deretter antar jeg at hver av disse segmentene sorteres og kan slås sammen igjen. Hvor er det kjøretidene \(\Omega(k\log k)\) og \(\Omega(n)\) kommer inn i dette bildet? Er det oppdelingen av elementer inn i de respektive segmentene som bruker \(\Omega(k\log k)\) tid og sorteringen av elementene innad i segmentene som bruker \(\Omega(n)\)? Det er mulig at jeg er helt på bærtur her men har grublet på dette spørsmålet en stund nå…

Vel, det med \(\Omega(n)\) kommer bare av at du naturligvis må se på alle verdiene for å finne ut hvor de skal være, så den biten er ikke så interessant.

Og det er ikke snakk om å analysere hvordan en hypotetisk algoritme fungerer her – dvs., ikke snakk om å se på oppdeling og sortering hver for seg, etc. Vi bruker en reduksjon fra sortering. Det er det, og bare det, som gir den nedre grensen på \(\Omega(k\log k)\). Hvorfor? Fordi vi vet at det er umulig å sortere \(k\) elementer bedre enn dette, og algoritmen som beskrevet kan brukes til å sortere \(k\) elementer. QED.

«… det med \(\Omega(n)\) kommer bare av at du naturligvis må se på alle verdiene for å finne ut hvor de skal være»

Beklager men strever fortsatt med å se denne. For å få \(\Omega(n)\) tid så må vi sammenligne alle elementene én gang? Altså f. eks med insertion sort så vil vi ha en best-case \(\Omega(n)\) kjøretid dersom alle elementene er allerede sortert. Men er ganske sikker på at det ikke er tilfellet du har beskrevet ovenfor siden du snakker om å plassere de forskjellige verdiene hvor de skal være, men er ikke dette en sortering?

Best-case er ikke så interessant (se LF). Selv om oppgaven ikke var tydelig nok på det, så er det worst-case vi er ute etter. Uansett: Om algoritmen skal være sikker på å bli rett, så må den utføre \(\Omega(n)\) operasjoner også i best-case. La oss i den ikke gjorde det – at den f.eks. hadde en kjøretid på \(O(\log n)\). Da vil den ikke engang kunne lese input. Med få unntak (der vi har gjort forarbeide, og dermed kan ignorere deler av dataene, som f.eks. med binærsøk) så har alle algoritmene i pensum – og de fleste andre – en lineær nedre grense.

«… du snakker om å plassere de forskjellige verdiene hvor de skal være, men er ikke dette en sortering?»

Det er ingen motsetning mellom det. Du har \(n\) elementer. Du får dem inn i en eller annen rekkefølge. De skal ut i en eller annen rekkefølge. Hvis ingen av elementene står på samme plass i input og en lovlig output, så må du flytte på alle sammen. Som gir en grense på \(\Omega(n)\). Som sagt, denne biten av løsningen er ikke så spennende, og jeg tror kanskje du gjør den mer komplisert enn den er – det følger bare av at algoritmen må gjøre et eller annet (lese, sammenligne, flytte, what-have-you) med alle elementene i input.

Logikken her følger ganske greit fra kapittel 8.1, «Lower bounds for sorting». I Theorem 8.1 ser du at det ikke går an å sortere bedre enn \(\Omega(n\log n)\). Eller, dersom vi kaller antall elementer \(k\), så går det ikke an å sortere dem bedre enn \(\Omega(k\log k)\) i verste tilfelle.

Dette er altså gitt. Den kreative innsikten i denne oppgaven er at algoritmen hans kan brukes til å sortere k elementer. Og det vet vi (fra Theorem 8.1) at den umulig kan gjøre bedre enn \(\Omega(k\log k)\). Mer enn dette er det egentlig ikke.

Hvis algoritmen hans kunne løse problemet bedre, kunne du altså ta et vilkårlig sorteringsproblem, gjøre det om til den typen problem Lurvik kan løse, og så få ham til å løse det. Du ville da ha løst sorteringsproblemet ditt bedre enn det som er matematisk mulig. Derfor må påstanden til Lurvik være feil.

Henger meg på.

Så hva er da et godt/godkjent svar her? Kan en anta at han har funnet en velfungerende algoritme, hvor han må flytte alle elementene minst en gang, dvs., \(\Omega(n)\)? I tillegg må han sortere dem, hvor vi vet at den nedre grensen for sorteringsalgoritmer er \(\Omega(n\lg n)\).

Men, hvordan skal vi bruke/hvordan påvirker infoen om at vi skal legge dem i \(k\) segmenter, og hvor elementene i segmentet til venstre må være mindre enn dem til høyre osv? Og hvorfor blir det \(\Omega(k\lg n)\) istedenfor \(\Omega(n\lg n)\) (pluss \(n\)-en)?

Du må vise at algoritmen hans kan brukes til å sortere \(k\) elementer, og at du dermed får en nedre grense på kjøretiden som er \(\Omega(k\log k)\). Det er den viktigste nedre grensen her. Vi må også ha med \(\Omega(n)\) fordi det er en nedre grense for alle algoritmer som må behandle hele input, og siden vi kan risikere \(k\log k<n\). Men om du har skjønt at du her kan bruke den nedre grensen \(\Omega(k\log k)\) fordi algoritmen hans kan sortere \(k\) elementer, så er det antagelig nok til full score. (Du må nok også kort forklare hvordan den kan brukes til å gjøre dette – f.eks. ved å replikere hvert av de \(k\) elementene, eller bare ett av dem, så du totalt for \(n\) elementer.)