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

アルゴリズムとは何ですか？

1. A問題を解く、明確に定義された手順の有限の列
2. B数式を書くために設計されたプログラミング言語
3. Cグラフィカルなインターフェースをもつあらゆるコンピュータプログラム
4. D数値を格納するデータ構造

メモ化（memoisation）とは何ですか？

1. A関数が戻った後にメモリを解放すること
2. B再帰を自動的に等価なループに変換し、コールスタックを不要にすること
3. C関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
4. Dコードの各行の横にコメントを書くこと

0 から k の範囲の n 個の整数に対する計数ソート（counting sort）の実行時間は何ですか？

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

V 個の頂点と E 本の辺をもつグラフに対するベルマン－フォード法の時間計算量は何ですか？

1. AO(V³ × E)
2. BO(V × E)
3. CO(E log V)
4. DO(V + E)

O(n²) のアルゴリズムは O(n³) でもあると言うのは正しいですか？

1. Aはい。ただし n が 100 より小さい場合に限る
2. Bいいえ。Big O は常に関数の正確な増加率を述べなければならないから
3. Cいいえ。n が大きいとき n³ は n² より小さいから
4. Dはい。Big O は上界であり、n² は n³ より速く増加しないから

漸化式 T(n) = T(n − 1) + O(1) の解は何ですか？

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

シュトラッセンのアルゴリズムは、半分のサイズのブロックの再帰的な掛け算を 8 回ではなく 7 回にして行列を掛けます。実行時間は何ですか？

1. AΘ(n³)
2. BΘ(n²)
3. CΘ(n² log n)
4. DΘ(n^{log₂ 7})、約 n^2.81

どんな入力に対してもクイックソートの期待（expected）実行時間を O(n log n) にする手法はどれですか？

1. A常に先頭の要素を選ぶ
2. B左側にのみ再帰を使う
3. Cピボットを一様ランダムに選ぶ
4. Dクイックソートを実行する前に入力をソートする