計算複雑性

IT用語辞典バイナリ

計算複雑度

読み方：けいさんふくざつど
別名：計算複雑性
【英】computational complexity

計算複雑度とは、計算機が問題を計算するために要する手間を示す尺度のことである。

計算複雑度は、アルゴリズムの性能を評価する基準のひとつとして用いられている。ある問題を解決するために、複数のアルゴリズムを用いることができるとすれば、どのアルゴリズムを選択れば最も効率的に処理できるかを判断するための判断基準の一つとして、計算複雑度を利用することができる。

計算複雑度は、入力サイズの関数として示される。あるアルゴリズムについて、入力サイズがnのとき計算複雑度がnに比例するか、nの多項式で示されない場合、nが極端に大きくなると実用時間内では解けないアルゴリズムとなる。

なお、実用のソフトウェアにおいては、アルゴリズムの>計算複雑度に加えて、プログラムを実行するハードウェアの環境や、プログラム上でのアルゴリズムの実装方法などが複雑に関連する。

情報処理のほかの用語一覧

アルゴリズム：

ハッシュ法  関数  完全2分木  計算複雑度  ケーニヒスベルグの橋  基本交換法  降順

>>アルゴリズムカテゴリの他の用語

ウィキペディア小見出し辞書

計算複雑性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/11 19:57 UTC 版)

「アダマール変換」の記事における「計算複雑性」の解説

アダマール変換は高速アダマール変換を用いると O ( n log ⁡ n ) ( n = 2 m ) である。