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

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

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

あるループは i = 1 から始まり、i > n となるまで各反復で i を 2 倍にします。何回反復しますか？

1. A約 n / 2 回
2. B約 n² 回
3. C約 n 回
4. D約 log₂ n 回

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

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

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²)

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

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

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

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

巡回セールスマン問題はどのように分類されますか？

1. A決定版は NP 完全で、最適化版は NP 困難である
2. B決定版は P に属するが、最適化版は NP 完全である
3. C決定不能である
4. Dダイクストラ法がすべての都市を 1 回ずつ訪れて解くので、P に属する

どんな入力に対してもクイックソートの期待（expected）実行時間を O(n log n) にする手法はどれですか？

1. A常に先頭の要素を選ぶ
2. B左側にのみ再帰を使う
3. Cピボットを一様ランダムに選ぶ
4. Dクイックソートを実行する前に入力をソートする