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

あるアルゴリズムの実行時間は O(n) です。この増加は何と呼ばれますか？

1. A線形
2. B対数的
3. C定数
4. D2 乗

次の実行時間のうち、多項式時間はどれですか？

1. AO(nⁿ)
2. BO(n³)
3. CO(n!)
4. DO(2ⁿ)

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

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

1、3、4 の硬貨で金額 6 をつくるとき、貪欲な「最大の硬貨から」方式は最適解と比べて何枚の硬貨を使いますか？

1. A貪欲法は 3 枚、最適解は 3 枚
2. B貪欲法は 3 枚、最適解は 2 枚
3. C貪欲法は 2 枚、最適解は 2 枚
4. D貪欲法は 4 枚、最適解は 3 枚

到達可能な基底部をもたない再帰関数について、正しい記述はどれですか？

1. AO(1) 時間で動作する
2. B自動的に 0 を返す
3. Cコンパイラが常にそれを、安全に終了するループに変換する
4. Dコールスタックがオーバーフローするまで自分自身を呼び続ける

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

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

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)
3. CO(n √n)
4. DO(n²)

ハッシュテーブルの平均探索時間が O(1) なのに、最悪の場合は O(n) になるのはなぜですか？

1. Aキーを先にソートする必要があるから
2. B配列のアクセスが O(n) だから
3. C多くのキーが同じバケットで衝突（collision）する可能性があるから
4. Dハッシュ関数が遅いから