レポート課題

二つの問題を例示し、どちらが難しいかを比較しなさい。 但し、偶数判定問題と、10進数や2進数での最下位桁の偶数判定問題の組、並びに類 似した問題を除く。

締切

2021 年 7 月 21 日

提出先

BOX

注意

1. 同一問題に対する複数のアルゴリズムの比較をする課題ではありません。
2. 問題の計算量と、アルゴリズムの計算量は別です。 一つの問題に対して複数のアルゴリズムが存在するため、 粗悪なアルゴリズムの計算量を無根拠に問題の計算量を表す指標とすること はできません。
3. ある問題を考え、それを解くアルゴリズムがあったとしても、そのアルゴリ ズム自体の計算量がその問題の計算量と一致するわけではありません。 特に、問題を解くための必要最低限度の時間を求めるのは困難です。