アルゴリズム・イントロダクション第2章第2節の練習問題

2.2-1

Θ(n³)

2.2-2

def selection_sort(A):
    n = len(A)
    for i in range(n-1):
        minimum = i
        for j in range(i+1, n):
            if A[minimum] > A[j]:
                minimum = j
        A[i], A[minimum] = A[minimum], A[i]

ループ不変式は、「第3-8行のforループが開始されるとき、部分配列 A[0 .. i-1] には A の小さい方から i 個の値がソートされて格納されている」。

ループ不変式により、n-1個の交換が終わった時点で部分配列 A[0 .. n-2] には A の小さい方から n-1 個の値が格納されているから、 A[n-1] は最大値である。ソート後、最大値は A[n-1] にあればよいので、n-1個の交換が終わった時点でソートを終了してよい。

入力の配列Aの中身にかかわらず、第3-8行のループはn-1回、第5-7行のforループはそれぞれ n-i-1 回実行される。 $\inline \sum_{i=0}^{n-2} (n-i-1) = \frac{n(n-1)}{2}$ より、最良実行時間および最悪実行時間はΘ(n²)

2.2-3

探索される配列の大きさを n とする。

k番目に目的の値がある場合、チェックされる要素は k 個。また、目的の値が見つからない場合にチェックされる要素は n 個。これら全てが等確率で起きるから、平均で $\inline \frac{n}{n+1}+ \sum_{i=1}^{n} \frac{i}{n+1} = \frac{n}{n+1}+\frac{n}{2}$ 個の要素がチェックされる。最悪の場合は目的の値がない場合なので n 個。

$\inline \frac{n}{n+1}+\frac{n}{2} = \Theta(n)$ 、また n = Θ(n) だから、順次探索法の平均実行時間および最悪実行時間は Θ(n)

2.2-4

分からない。考える。