成長のオーダー
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/13 15:58 UTC 版)
詳細は「ランダウの記号」を参照 大まかに言えば、あるアルゴリズムの入力サイズ n がある特定の値を超えたとき、その成長率がある数学関数のオーダーであるとは、その関数 f(n) に正の定数をかけた値がそのアルゴリズムの実行時間の上限（英語版）を与えることを意味する。言い換えれば、入力サイズ n が n0 より大きいとき、そのアルゴリズムの実行時間は c × f(n) を越えない（cは定数）。この概念はO記法で表現されることが多い。例えば、挿入ソートの実行時間は二次関数的に成長（英語版）するので、挿入ソートのオーダーは O(n2) と言える。 O記法はアルゴリズムの最悪の場合を表現するのによく使われるが、平均的なケースを表すのに使われることもある。例えばクイックソートの場合、最悪では O(n2) だが、平均では O(n log n) となる。
※この「成長のオーダー」の解説は、「アルゴリズム解析」の解説の一部です。
「成長のオーダー」を含む「アルゴリズム解析」の記事については、「アルゴリズム解析」の概要を参照ください。
ウィキペディア小見出し辞書の「成長のオーダー」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 成長のオーダーのページへのリンク
