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

n 個の要素を持つ未ソートの配列に対する線形探索（linear search）の時間計算量（最悪の場合）は何ですか？

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

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

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

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

1. A線形
2. B定数
3. C2 乗
4. D対数的

重みなしグラフでの幅優先探索（BFS）で求められるものはどれですか？

1. A始点ノードからの辺の数で測った最短経路
2. B最小全域木
3. C負の辺の重みを含むグラフでの最短経路
4. Dすべてのグラフにおけるトポロジカル順序

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

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

多くのライブラリのソート関数が、非常に小さな部分配列では挿入ソートに切り替えるのはなぜですか？

1. A挿入ソートは最悪の場合 O(n log n) だから
2. B大きな入力では、挿入ソートは他のどのソートアルゴリズムよりメモリが少なくて済むから
3. C挿入ソートはオーバーヘッドが小さく、小さな入力やほぼソート済みの入力で速いから
4. D再帰アルゴリズムは 10 要素未満の配列を扱えないから

log(n!) について正しい評価はどれですか？

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

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

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