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

n が大きくなるとき、最もゆっくり増加するのはどれですか？

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

メモ化（memoisation）とは何ですか？

1. A関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
2. Bコードの各行の横にコメントを書くこと
3. C関数が戻った後にメモリを解放すること
4. D再帰を自動的に等価なループに変換し、コールスタックを不要にすること

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

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

ソート済み配列で、両端から 1 つずつポインタを内側へ動かして、和が目標値になる 2 つの要素を探します。時間計算量は何ですか？

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

ボトムアップの表を使って n 番目のフィボナッチ数を計算する時間計算量は何ですか？

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

安定（stable）なソートアルゴリズムはどれですか？

1. A選択ソート（一般的な版）
2. Bクイックソート（一般的なインプレース版）
3. Cヒープソート
4. Dマージソート

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

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

最短単純路は多項式時間で見つけられます。一般のグラフで 2 頂点間の最長単純路を見つけることについて、何が知られていますか？

1. ANP 困難である
2. B常に O(V + E) で解ける
3. C重みの符号を反転すればダイクストラ法で解ける
4. D決定不能である