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

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

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

平均実行時間は何を表しますか？

1. Aサイズ n の入力の与えられた分布に対する期待所要時間
2. B最良の場合と最悪の場合の実行時間の中間の値
3. C平均的な長さの入力に対する所要時間
4. D最も一般的なコンピュータでの所要時間

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

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

k 進数で d 桁の n 個の整数に対する LSD 基数ソートの実行時間は何ですか？

1. AO(n log n)
2. BO(dn log k)
3. CO(n²)
4. DO(d(n + k))

問題が最適部分構造をもつとはどういう意味ですか？

1. A問題の最適解がちょうど 1 つで、すべての部分問題がそれを共有しているから
2. B問題を定数時間で解ける
3. C最適解を部分問題の最適解から構成できる
4. Dすべての部分問題が同じサイズである

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

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

n が大きいとき、n! と 2ⁿ はどのように比較されますか？

1. A2ⁿ は n! より速く増加する
2. Bn! は 2ⁿ より速く増加する
3. Cn! は O(n²) である
4. D同じ速さで増加する

極大マッチングのすべての辺の両端点をとると頂点被覆が得られます。この被覆はどれくらいよいですか？

1. A最小値の高々 log n 倍
2. B最適解と比べた品質は不明
3. C最小頂点被覆のサイズの高々 2 倍
4. D常に最小頂点被覆