関数の漸近的振舞い最悪値評価を理解しているだろうか。
過去記事から、アルゴリズムの評価方法について理解していることだろう。
関数の漸近的振舞いと最悪値評価の説明ができるだろうか。
今回は、関数の漸近的振舞いを表すランダウの記号、いわゆるビッグ・オー記法と最悪値評価を書き溜め、
新しく計算機科学を学ぶ人のためのマイルストーンを残していく。
最悪値評価
いわゆる「最大でも〜」という評価方法である。
誕生日に友達を家に招待するとき、招待状は何枚必要になるかを考えるとき、
友達が数人なら指を折って数えるだけだが、友達リストがある程度大きくなってしまうと、
「最大でも〇〇枚が必要になり、そこから不要だと思われる人物の数だけ減らしていく」という方法を取ったほうがよいだろう。
アルゴリズムの実行時間解析の際にも広く用いられる手法である。
例えば、
「このアルゴリズムは、最大でもこれだけ実行時間を要する」
といった感じだ。
関数の漸近的振舞い（ランダウの記号）
先程の最悪値評価と組み合わせて用いられる事が多い。
ランダウの記号（ランダウのきごう、英: Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。
ランダウの記号、は変数 x を極限に飛ばした時の関数 f の振る舞い（漸近的挙動）を、別の関数 g を目安にして記述する目的で用いられる。
(Wikipediaより)
ランダウの記号の厳密な説明については別途参照されたい。
ポイントとしては、下記の２点である。
- 関数の中で最も急速に増加する項だけ対象とする
- 定数係数は無視する
２つのポイントを用いて、
計算量をＯ（オーダ）という記号で表す（ビッグ・オー記法）。
たとえば、
データ件数が２倍、３倍と増えると、計算量も２倍、３倍になるならＯ（n）である。
データ件数が２倍、３倍と増えた時、計算量が４倍、９倍となるならＯ（ｎ^２）となる。
Ｏ（n）とＯ（n^2）と表記することで
どちらのアルゴリズムが良いかの判断が容易になる。
関数の漸近的振舞いと最悪値評価を説明してください。
さて、先程の説明を読んだ人は、関数の漸近的振舞いと最悪値評価を説明できますね。
計算量はどういった記号で表されますか？ポイントは２つありましたね。
ノートやメモに書くでも、Twitterに呟くでもYoutubeにアップロードするでも構いません。
今日知った情報をアウトプットしてみましょう。
じゃあね〜〜〜。