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

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

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

分割統治アルゴリズムの 3 つのステップは何ですか？

1. A推測、確認、反復
2. B分割、統治、結合
3. Cソート、探索、返却
4. D読み込み、計算、書き出し

すでにソート済みの配列に対する挿入ソートの最良時間計算量は何ですか？

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

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

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

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

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

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

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

ナップサック問題のどの変種で、「重さあたりの価値の順に品物をとる」という貪欲な規則が常に最適解を与えますか？

1. A品物を分割できる分数ナップサック問題
2. B品物を必ず丸ごととらなければならない 0/1 ナップサック問題
3. Cどちらの変種でもない
4. D両方の変種

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

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