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

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

1. ALittle omega
2. BBig Theta
3. CBig Omega
4. DBig O

n 個の数からなる未ソートの配列で最大値を見つける時間計算量は何ですか？

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

f(n) = Θ(g(n)) はどういう意味ですか？

1. Af は g より真に速く増加する
2. Bすべての n について f は常に g より小さいので、g は上からは抑えるが下からは決して抑えない
3. Cf は g と同じ速さで増加し、上下から g の定数倍で抑えられる
4. Df は g より真に遅く増加する

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

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

動的計画法（dynamic programming）が有効なのは、問題が次の性質を持つときです。

1. Aループが一つだけ
2. Bランダムな入力のみ
3. C部分問題がまったくないので、1 ステップで解ける
4. D重複する部分問題と最適部分構造

満杯になると容量を2倍にする動的配列に要素を追加する操作の償却（amortised）時間計算量は何ですか？

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

ある NP 完全問題に対する多項式時間アルゴリズムを誰かが見つけたら、何が導かれますか？

1. ANP のすべての問題が多項式時間で解けることになり、P = NP となる
2. Bすべての指数時間アルゴリズムがただちに線形時間で動くようになる
3. C停止問題が決定可能になる
4. Dその 1 つの問題だけが P に移る

for i = 1 to n: for (j = i; j ≤ n; j = j + i) do O(1) work の時間計算量は何ですか？

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