多項式時間とは計算量の内 アルゴリズム内の全処理数が多項式回相当の物、 指数時間とは指数関数回相当の物です。 例として 最大値を求めるアルゴリズム 小さい順に数を整列させるアルゴリズム は多項式時間、 パスワード解読のアルゴリズム は指数時間で計算されます。 具体的な処理数の数え方と関連してP≠NP問題まで、 わかりやすく説明します。 多項式時間とは 10個のランダムな数字から最大値を求めるアルゴリズムを考えます。 2、6、17、8、9、3、10、12、5、1 が入力されたとして、 この中から一番大きな数 ...
