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

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

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

ある O(n²) アルゴリズムは n = 1000 で 1 秒かかります。n = 2000 ではおよそ何秒かかりますか？

1. A2 秒
2. B1 秒
3. C8 秒
4. D4 秒

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

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

重みなしグラフでの幅優先探索（BFS）で求められるものはどれですか？

1. Aすべてのグラフにおけるトポロジカル順序
2. B負の辺の重みを含むグラフでの最短経路
3. C最小全域木
4. D始点ノードからの辺の数で測った最短経路

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

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

貪欲法（greedy algorithm）の説明として正しいものはどれですか？

1. A各ステップで局所的に最良の選択をする
2. B可能なすべての解を試す
3. C常に最適解を与える
4. D再帰のみを使用する

極大マッチングのすべての辺の両端点をとると頂点被覆が得られます。この被覆はどれくらいよいですか？

1. A最適解と比べた品質は不明
2. B最小頂点被覆のサイズの高々 2 倍
3. C最小値の高々 log n 倍
4. D常に最小頂点被覆

単方向連結リストでは、二分探索が O(log n) 時間にならないのはなぜですか？

1. A連結リストのノードでの比較は遅いから
2. Bインデックスによる直接アクセスがないので、中央の要素に到達するのに O(n) ステップかかるから
3. C二分探索には少なくとも 2 倍のメモリが必要だから
4. D連結リストはソートできないから