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

それぞれ n 回実行される二重の入れ子ループを持つアルゴリズムの計算量は、通常どれですか？

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

空間計算量（space complexity）が測るものはどれですか？

1. Aコードの行数
2. Bコンパイル後のプログラムファイルのディスク容量
3. Cコンピュータの物理的な大きさ
4. D入力が大きくなるにつれてアルゴリズムが必要とするメモリ量

ある O(n²) アルゴリズムは n = 1000 で 1 秒かかります。n = 2000 ではおよそ何秒かかりますか？

1. A2 秒
2. B1 秒
3. C4 秒
4. D8 秒

標準的な 3 重ループで 2 つの n × n 行列を掛ける時間計算量は何ですか？

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

プリム法は最小全域木をどのように構築しますか？

1. A幅優先探索を実行し、BFS 木を残す
2. B閉路がなくなるまで最も高い辺を取り除く
3. C開始頂点から 1 本の木を成長させ、木から出る最も安い辺を加える
4. Dすべての辺を重みでソートし、森の中で閉路をつくる場合を除いて 1 本ずつ加える

漸化式 T(n) = T(n/2) + O(1) の解は何ですか？

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

V 個の頂点と E 本の辺をもつグラフで、二分ヒープを用いたダイクストラ法の実行時間は何ですか？

1. AO(V³)
2. BO(V + E)
3. CO((V + E) log V)
4. DO(V × E)

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

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