AU logo

Algoritmer og Datastrukturer

Multiple-choice opgaver

Amortiseret analyse

Spørgsmål 1 - Linear probing i dynamiske arrays

Antag vi ønsker at gemme en mængde af $n$ tal vha. hashing med linear probing i et array af størrelse $N$. Vi garanterer at arrayet altid er mellem 1/4 og 3/4 fyldt. Hvis der bliver færre end $N/4$ eller flere end $3N/4$ tal i mængden genindsætter vi alle tal i et nyt array af størrelse $2n$, dvs. det nye array er 1/2 fyldt. Angiv en potentiale funktion hvormed man kan vise at det totalle antal genindsættelser i hashtabellerne er amortiseret $O(1)$ per indsættelse og slettelse i mængden.
$N-n$ $n$ $\frac{3}{4}N-n$ $n-\frac{1}{4}N$ $2|N-2n|$ $(n-\frac{1}{4}N)(\frac{3}{4}N-n)$
$\Phi=$

Spørgsmål 2 - Rød-sorte træer med Delete i amortiseret konstant tid

Rød-sorte søgetræer understøtter Insert og Delete på et træ med $n$ elementer i worst-case tid $O(\log n)$. Angiv en potentialefunktion hvormed man kan argumentere for at Insert tager amortiseret tid $O(\log n)$ og Delete tager amortiseret $O(1)$ tid.
$\log n$ $n$ $\sum_{i=1}^n i$ $\sum_{i=1}^n \log i$ $n+\log n$
$\Phi=$

Spørgsmål 3 - Binære heaps i dynamiske arrays

Antag at en binær max-heap med $n$ elementer er gemt i de første $n$ indgange i et array af størrelsen $N$. Operationerne Insert og Extract-Max implementeres som for en standard binær max-heap, på nær Insert når $n=N$, hvor heapen først kopieres over i et nyt array af dobbelt størrelse $2N$, dvs. $N$ fordobles, hvorefter Insert operationen udføres som for en standard binær max-heap. Angiv en potentialefunktion hvormed man kan argumentere for at Insert tager amortiseret $O(\log n)$ tid og Extract-Max tager amortiseret $O(1)$ tid.
$N-n+\log n$ $n\log n$ $|2n-N|+\sum_{i=1}^n \log i$ $N+n\log n$ $n+\log n$
$\Phi=$

Spørgsmål 4 - Binære tællere i dynamiske arrays

Betragt et array $A[0..N-1]$ af længde $N$, hvor hver indgang er enten 0 eller 1. $A$ opfattes som et binært tal med værdien $n$, hvor $n=\sum_{i=0}^{N-1} 2^i\cdot A[i]$. Operationen Inc$(A)$ øger værdien af $n$ med 1 ved at flippe $A[0],A[1],...$ indtil det første $A[i]$ flippes fra 0 til 1. Hvis alle indgange i $A$ indeholdt 1 (dvs. $n=2^N-1$ før Inc$(A)$ udføres), så kopieres $A$ over i nyt array af dobbelt størrelse $2N$, hvor alle $A[i]=0$ bort set fra $A[N]=1$. Angiv en potentialefunktion kan man argumentere for at Inc tager amortiseret $O(1)$ tid. I nedenstående betegner $k$ antal $A[i]=1$, dvs. $k=|\{ i \mid A[i]=1\}|$.
$k$ $n$ $N-k$ $\log n-\frac{1}{2}N$ $|2k-N|$
$\Phi=$

Spørgsmål 5 - Slettelser i binære max-heaps

En binær max-heap understøtter Insert og Heap-Extract-Max i worst-case $O(\log n)$ tid. Angiv en potentiale funktion så Insert tager amortiseret $O(\log n)$ tid og Heap-Extract-Max amortiseret $O(1)$ tid.
$\log n$ $n$ $n+\log n$ $n\log n$ $n-\log n$
$\Phi=$

0% besvaret