1.4 Kjøretids- og teori-fakta — sant/usant og antigjettings-strategi

$$\log_2 n \text{ nivåer} \times O(n) \text{ per nivå} = O(n \log n)$$

Dette gjelder verste tilfelle, ikke bare forventet. Det er en av de få
sorteringene der de to sammenfaller, og det er derfor den brukes som referanse.

Gå gjennom arrayet én gang og sammenlign hvert element med det neste. Er alle
naboparene i orden, er hele arrayet sortert. Det tar $n - 1$ sammenligninger,
altså $O(n)$.

Faktumet dukker opp som sant/usant-punkt, og det brukes som byggekloss i
Del 2-løsninger: «sortér i $O(n \log n)$ og skann i $O(n)$» er en fullt lovlig
strategi der den lineære løsningen ikke finnes.

Binærsøk hopper til midten av søkeområdet, kaster halvparten, og gjentar — derfor
$O(\log n)$. Men det forutsetter at du kan hoppe til et vilkårlig element i
konstant tid.

I et array koster A[i] $O(1)$, så binærsøk er $O(\log n)$. I en lenket
liste må du følge pekerne fra starten for å komme til midten, og det koster
$O(n)$ per hopp — da er binærsøk ikke bare unyttig, det er tregere enn å skanne
listen. Derfor: binærsøk er raskere på array enn på lenket liste.

Kvikksortering deler arrayet om et pivotelement. Treffer pivoten omtrent midt på
hver gang, blir det $\log n$ nivåer og $O(n \log n)$ totalt — det forventede
tilfellet.

Men treffer pivoten hver gang ytterst (for eksempel om arrayet allerede er
sortert og du velger første element), blir det $n$ nivåer, og kjøretiden blir
$O(n^2)$. Påstanden «kvikksortering er $O(n \log n)$ i verste tilfelle» er
derfor usann, og den er en fast distraktor.

Et binærtre som fylles nivå for nivå fra venstre (kalt strukturkravet), og
der hver node er mindre enn eller lik begge barna sine (ordningskravet).

Treet lagres i et array uten pekere: roten på indeks 0, og for elementet på
indeks $i$ er forelderen på $\lfloor (i-1)/2 \rfloor$ og barna på $2i+1$ og
$2i+2$. Merk indekseringen fra 0 — andre bøker starter på 1 og får andre
formler.

I en heap gjelder ordningen mellom forelder og barn: forelderen er mindre enn
eller lik begge barna i en min-heap. Det er ingen ordning mellom søsken, og ingen
ordning venstre mot høyre.

Dette skiller heapen fra søketreet, der ordningen nettopp er venstre mot høyre.
Å blande de to er felle #9 i bokas register — å forveksle søketre-ordenen med
heap-ordenen.

Ordningskravet gjelder hele veien nedover, så ingen node kan være mindre enn
roten. Å lese det minste er derfor $O(1)$: du slår opp på indeks 0.

Å fjerne det er dyrere, $O(\log n)$, fordi strukturen må gjenopprettes
etterpå.

Ordningskravet sier ingenting om hvor det største elementet ligger, annet enn at
det må være et blad. Men en heap med $n$ elementer har omtrent $n/2$ blader, og
du må sjekke alle.

Derfor er påstanden «du kan finne det største elementet i en min-heap i
$O(\log n)$» usann — det koster $O(n)$. Dette er et av de hyppigste
sant/usant-punktene i faget.

Det nye elementet legges bakerst i arrayet og bobler oppover mot roten så lenge
det er mindre enn forelderen sin. Antall steg er høyden på treet.

Et binærtre med $n$ noder som fylles nivå for nivå har høyde
$\lfloor \log_2 n \rfloor$, så innsetting er $O(\log n)$ — også i verste
tilfelle.

Det ser ut som $n$ innsettinger à $O(\log n)$, altså $O(n \log n)$. Men bygger du
nedenfra og opp, gjør de fleste nodene nesten ingenting: halvparten er blader og
flytter seg ikke i det hele tatt, en firedel flytter seg høyst ett nivå, og så
videre. Summen blir $O(n)$.

Påstanden «å bygge en heap fra et vilkårlig array tar $O(n \log n)$» er derfor
usann — den er den vanligste distraktoren på hele Del 1.

Å snu arrayet snur ikke forelder-barn-relasjonene, for de er bestemt av
indeksformlene $\lfloor (i-1)/2 \rfloor$, $2i+1$ og $2i+2$ — ikke av innholdet.
Etter reversering peker formlene på helt andre elementer, og ordningskravet
gjelder ingen vei.

Påstanden er derfor usann, og den er en fast distraktor. Vil du ha en
max-heap, må du bygge den med motsatt sammenligning.

Et balansert søketre — for eksempel et AVL-tre — holder høyden på $O(\log n)$.
Det minste elementet ligger lengst til venstre og finnes i $O(\log n)$, og
innsetting er $O(\log n)$.

Påstanden «et AVL-tre kan brukes som prioritetskø med samme orden som en heap»
er derfor sann. Heapen vinner likevel i praksis, på konstantfaktorer og
minnebruk — men ikke i $O$-klasse.

Problemene som kan løses av en algoritme med polynomisk kjøretid — altså
$O(n^k)$ for en fast $k$: $O(n)$, $O(n^2)$, $O(n^3)$ og så videre.

Alt du har møtt i denne boka så langt, ligger i $P$. Grensen går ved
eksponentiell tid som $O(2^n)$, som ikke er polynomisk.

Problemene der et foreslått ja-svar kan kontrolleres i polynomisk tid. Får du
utlevert en løsning, kan du sjekke om den holder, raskt — selv om du ikke vet
hvordan du skulle funnet den.

Merk at $NP$ ikke betyr «ikke-polynomisk». Det står for «ikke-deterministisk
polynomisk», og definisjonen handler om kontroll, ikke om løsning.

Et sertifikat er det foreslåtte svaret — for eksempel en konkret rundtur. En
verifikator er prosedyren som kontrollerer det.

Kravet for at et problem skal være i $NP$, er at det finnes en verifikator med
polynomisk kjøretid. Å skrive en slik verifikator er en oppgavetype i seg selv,
og den kommer i Del 7.

De vanskeligste problemene i $NP$: et problem er NP-komplett hvis det ligger i
$NP$, og alle andre problemer i $NP$ kan reduseres til det i polynomisk tid.

To konsekvenser som testes direkte: alle NP-komplette problemer er
polynomtidsreduserbare til hverandre (sant), og løser du ett av dem i
polynomisk tid, har du løst dem alle — altså $P = NP$ (sant).

Retningen er alt. Skal du vise at et nytt problem er vanskelig, reduserer du
fra et kjent vanskelig problem til ditt. Å gjøre det motsatt beviser
ingenting — det er felle #8 i bokas register.

Det er ikke bevist at $P = NP$, og det er ikke bevist at
$P \neq NP$. Spørsmålet er åpent.

Begge påstandene «det er bevist at $P = NP$» og «det er bevist at $P \neq NP$»
er derfor usanne. Dette er det enkleste punktet i hele bolken, og det er
også det som oftest kommer.

Oppgavetypen der du skal markere sant eller usant på korte påstander om
kjøretid, datastrukturer og kompleksitetsteori. Har kommet i alle sju settene,
som regel med flere punkter per sett.

Rettes automatisk og er skalert mot gjetting, så gjenkjenning holder ikke —
faktaene må sitte sikkert.

Antallet riktige som gir null poeng, typisk halvparten av påstandene: 16 av 32,
11 av 22, 9 av 18. Formen er $2 \cdot \max(n - k,\ 0)$, der $k$ er terskelen.

Praktisk regel: poengsummen din er omtrent «antall du kan sikkert, minus
terskelen, ganger to». Det er også den eneste størrelsen du kan påvirke før
eksamen.