AU logo

Algoritmer og Datastrukturer

Multiple-choice opgaver

Mergesort og quicksort

Spørgsmål 1

Give the best correct bound on these quantities related to Mergesort.
$\mathcal{O}(\log n)$ $\mathcal{O}(n)$ $\mathcal{O}(n\log n)$ $\mathcal{O}(n^2)$
Number of levels of recursion, best case.
Number of levels of recursion, worst case.
Time to perform the Merge operation, best case.
Time to perform the Merge operation, worst case.

Spørgsmål 2

Nedenstående spørgsmål vedrører Randomized Quicksort på input af størrelse $n$.
$\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ $\Theta(n^2)$
Worst-case antal kald til Partition proceduren
Forventede antal kald til Partition proceduren
Forventede tid for Randomized Quicksort
Worst-case tid for Randomized Quicksort

0% besvaret