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

増加の下界（lower bound）を表す記法はどれですか？

1. AΘ（Big Theta）
2. BO（Big O）
3. Co（little o）
4. DΩ（Big Omega）

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

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

ある操作が O(1) 時間で動作するとはどういう意味ですか？

1. A実行時間 1 秒あたりちょうど 1 要素を処理する
2. B常にちょうど 1 秒かかる
3. C一度しか実行できない
4. D実行時間が入力サイズとともに増加しない

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

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

for i = 1 to n: (j = 1; while j < n: j = j × 2) の時間計算量は何ですか？

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

ワーシャル－フロイド法は何を、どれくらいの速さで計算しますか？

1. A1 つの始点から他のすべての頂点への最短経路を O(V + E) で
2. Bトポロジカル順序を O(V²) で
3. Cすべての頂点対の間の最短経路を O(V³) で
4. D最小全域木を O(E log V) で

マスター定理を用いると、T(n) = 8T(n/2) + O(n²) の解はどれですか？

1. AΘ(n²)
2. BΘ(n log n)
3. CΘ(n³)
4. DΘ(n² log n)

一部の辺の重みが負のとき、ダイクストラ法が誤った結果を出すことがあるのはなぜですか？

1. A無向グラフでしか動作しないから
2. B負の数は優先度付きキューに格納できないから
3. C頂点は取り出された時点で確定するが、後の負の辺によってより短い経路が得られる可能性があるから
4. D負の辺があるたびに無限ループに陥るから