解答つきアルゴリズムと計算量ワークシート

それぞれ n 回実行される二重の入れ子ループを持つアルゴリズムの計算量は、通常どれですか？

1. AO(n²)
2. BO(2n)
3. CO(n)
4. DO(log n)

n 個の要素を持つ未ソートの配列に対する線形探索（linear search）の時間計算量（最悪の場合）は何ですか？

1. AO(1)
2. BO(log n)
3. CO(n²)
4. DO(n)

選択ソート（selection sort）はどのように動作しますか？

1. A配列を半分に分け、それらをマージする
2. B未ソート部分の最小値を繰り返し見つけ、それを先頭に交換する
3. C順序が逆になっている隣り合う要素を繰り返し交換する
4. Dシフトによって各要素を成長していくソート済み部分に挿入する

ある関数は n 回反復するループを 1 つ実行し、その後別に n 回反復するループをもう 1 つ実行します。時間計算量は何ですか？

1. AO(n²)
2. BO(n)
3. CO(log n)
4. DO(2ⁿ)

ならし解析（amortised analysis）は何を測りますか？

1. A最良の入力に対するアルゴリズムのコスト
2. Bランダムな入力に対する期待コスト
3. C最悪の操作列にわたる操作 1 回あたりの平均コスト
4. D操作列のどこかにある、最もコストの高い 1 回の操作のコスト

安定（stable）なソートアルゴリズムはどれですか？

1. A選択ソート（一般的な版）
2. Bクイックソート（一般的なインプレース版）
3. Cマージソート
4. Dヒープソート

for i = 1 to n: for (j = i; j ≤ n; j = j + i) do O(1) work の時間計算量は何ですか？

1. AO(n log n)
2. BO(n √n)
3. CO(n)
4. DO(n²)

停止問題（halting problem）が示していることはどれですか？

1. Aすべてのプログラムはいずれ停止する
2. Bループは避けるべきである
3. C一部のプログラムは高速なコンピュータでより速く動作するので、停止するかどうかはハードウェアに依存するから
4. Dすべてのプログラムと入力について、それが停止するかどうかを判定できるアルゴリズムは存在しない