計算量けいさんりょうの基本きほん

導入どうにゅう

この講義こうぎで最重要さいじゅうようなのは、アルゴリズムの速はやさは、1 回かいの実行時間じっこうじかんではなく、入力にゅうりょくサイズが大おおきくなったときにどう増ふえるかで見みることです。

同おなじ問題もんだいを解とくアルゴリズムでも、入力にゅうりょくが小ちいさいうちは差さが目立めだたなくても、大おおきくなると急激きゅうげきに差さが開ひらくことがあります。この増ふえ方かたを見みるのが計算量けいさんりょうです。

用語ようごと定義ていぎ

時間じかん計算量けいさんりょうTime complexity とは、入力にゅうりょくサイズ $$n$$n に対たいして、処理回数しょりかいすうがどう増ふえるかを表あらわしたものです。

空間くうかん計算量けいさんりょうSpace complexity とは、追加ついかで必要ひつようになるメモリがどう増ふえるかを表あらわしたものです。

方針ほうしん

まず、実際じっさいに何回なんかい繰くり返かえすかに注目ちゅうもくします。そのあと、定数倍ていすうばいや低次ていじの項こうを無視むしして、増ふえ方かたの本質ほんしつだけを残のこします。

直感的ちょっかんてきな説明せつめい

線形探索せんけいたんさくは、最悪さいあくだと先頭せんとうから末尾まつびまで全部ぜんぶ見みるので、入力にゅうりょくが 2 倍ばいになれば仕事量しごとりょうもだいたい 2 倍ばいになります。これが $$O\left(n\right)$$O(n) です。

二分探索にぶんたんさくは、1 回かいの比較ひかくで候補こうほを半分はんぶんにするので、入力にゅうりょくがかなり増ふえても比較回数ひかくかいすうはゆっくりしか増ふえません。これが $$O\left(\log n\right)$$O(\log n) です。

厳密げんみつな説明せつめい

見分みわけ方かた

• 1 重じゅうループならまず $$O\left(n\right)$$O(n) を疑うたがいます。
• 2 重じゅうループならまず $$O\left(n^2\right)$$O(n^2) を疑うたがいます。
• 範囲はんいを半分はんぶんずつに削けずるなら $$O\left(\log n\right)$$O(\log n) です。
• 配列はいれつや表ひょうを追加ついかでどれだけ作つくるかを見みると、空間くうかん計算量けいさんりょうの見当けんとうがつきます。

最終形さいしゅうけい

一言ひとことでいうと

• 計算量けいさんりょうは、入力にゅうりょくが大おおきくなったときの増ふえ方かたでアルゴリズムを比くらべる道具どうぐです。

関連かんれんリンク