中山 111 年資管所 資料結構 參考答案

$n\le 1$：$comp1(n)=0$。

Best case（$n>1$，pivot 每次落在正中間）：$comp1(n)=2comp1\left(\frac{n-1}{2}\right)+(n-1)=\Theta (n\log n)$。

Worst case（$n>1$，pivot 每次為極值）：$comp1(n)=comp1(n-1)+(n-1)=\frac{n(n-1)}{2}=\Theta (n^2)$。

$comp2(n)$：best 與 average 皆為 ${\sum }_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}=\Theta (n^2)$（標準版回合數固定）；若採提前終止版，best case 為 $n-1$。

$exchange(n)$ 等於輸入的 inversion 數：best case（已排序）為 $0$；average case 為 $\frac{1}{2}\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{4}=\Theta (n^2)$。

NoCommon(A[1..n], B[1..m]):   // n >= m
    Sort(B)                    // O(m log m)
    for i = 1 to n:
        if BinarySearch(B, A[i]) found:
            return false
    return true

排序 $O(m\log m)$ 加 $n$ 次二分搜尋 $O(n\log m)$，因 $n\ge m$，總計 $O(n\log m)$。