計算量による分類
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/28 01:04 UTC 版)
「複雑性クラス」も参照 アルゴリズムは、入力長に対する計算時間で分類される。あるアルゴリズムは入力長に対して線形時間で完了する。また別のアルゴリズムは指数時間以上かかるし、場合によっては完了しないこともある。さらに、問題によっては計算量の異なる複数のアルゴリズムが存在するし、効率的なアルゴリズムが全く知られていない問題もある。問題によっては、別の問題への写像が存在する。以上のようなことから、計算量による分類は、アルゴリズムについてではなく、問題について行うのが適当とされている。つまり、問題を解く最善のアルゴリズムの計算量に基づいて、問題を分類する。
※この「計算量による分類」の解説は、「アルゴリズム」の解説の一部です。
「計算量による分類」を含む「アルゴリズム」の記事については、「アルゴリズム」の概要を参照ください。
ウィキペディア小見出し辞書の「計算量による分類」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 計算量による分類のページへのリンク
