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

標準的な配列ベースのマージソートは、どれだけの追加メモリを使いますか？

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

二分探索は入力に何を要求しますか？

1. A配列が正の数だけを含むこと
2. B配列がソートされていること
3. C配列の長さが 2 のべき乗であること
4. D配列の要素が 1000 個以下であること

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

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

単純な再帰の階乗関数 fact(n) = n × fact(n − 1) はどれだけのスタック領域を使いますか？

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

長さ m と n の文字列の最長共通部分列を求める標準的な動的計画法の時間計算量は何ですか？

1. AO(mn)
2. BO(2^m+n)
3. CO(mn log n)
4. DO(m + n)

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

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

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

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

巡回セールスマン問題はどのように分類されますか？

1. A決定版は NP 完全で、最適化版は NP 困難である
2. B決定不能である
3. Cダイクストラ法がすべての都市を 1 回ずつ訪れて解くので、P に属する
4. D決定版は P に属するが、最適化版は NP 完全である