【独習】関数の漸近的振舞いと最悪値評価

関数の漸近的振舞いと最悪値評価

関数の漸近的振舞い最悪値評価を理解しているだろうか。

過去記事から、アルゴリズムの評価方法について理解していることだろう。
関数の漸近的振舞いと最悪値評価の説明ができるだろうか。
今回は、関数の漸近的振舞いを表すランダウの記号、いわゆるビッグ・オー記法と最悪値評価を書き溜め、
新しく計算機科学を学ぶ人のためのマイルストーンを残していく。

広告

最悪値評価

いわゆる「最大でも〜」という評価方法である。
誕生日に友達を家に招待するとき、招待状は何枚必要になるかを考えるとき、
友達が数人なら指を折って数えるだけだが、友達リストがある程度大きくなってしまうと、
「最大でも〇〇枚が必要になり、そこから不要だと思われる人物の数だけ減らしていく」という方法を取ったほうがよいだろう。

アルゴリズムの実行時間解析の際にも広く用いられる手法である。
例えば、
「このアルゴリズムは、最大でもこれだけ実行時間を要する」
といった感じだ。

関数の漸近的振舞い(ランダウの記号)

先程の最悪値評価と組み合わせて用いられる事が多い。

ランダウの記号(ランダウのきごう、英: Landau symbol)は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。

ランダウの記号、は変数 x を極限に飛ばした時の関数 f の振る舞い(漸近的挙動)を、別の関数 g を目安にして記述する目的で用いられる。
(Wikipediaより)

ランダウの記号の厳密な説明については別途参照されたい。
ポイントとしては、下記の2点である。

  • 関数の中で最も急速に増加する項だけ対象とする
  • 定数係数は無視する

2つのポイントを用いて、
計算量をO(オーダ)という記号で表す(ビッグ・オー記法)。


たとえば、
データ件数が2倍、3倍と増えると、計算量も2倍、3倍になるならO(n)である。
データ件数が2倍、3倍と増えた時、計算量が4倍、9倍となるならO(n^2)となる。

O(n)とO(n^2)と表記することで
どちらのアルゴリズムが良いかの判断が容易になる。

関数の漸近的振舞いと最悪値評価を説明してください。

さて、先程の説明を読んだ人は、関数の漸近的振舞いと最悪値評価を説明できますね。
計算量はどういった記号で表されますか?ポイントは2つありましたね。

ノートやメモに書くでも、Twitterに呟くでもYoutubeにアップロードするでも構いません。
今日知った情報をアウトプットしてみましょう。


じゃあね〜〜〜。