時間計算量の話

背景

プログラマーなら一度はBigO記法を聞いたことがあるだろう。

これはコードのシンプルさ効率の良さを表す１つの指標となっている。

ふとしたことをきっかけにBigO以外にも表記があることを知ったのでご紹介。

BigO記法に似たものたち

BigO

学術的に、計算量の上限。これよりも大きくはならない。

BigΩ

学術的に、計算量の下限。これよりも小さくはならない。

BigΘ

学術的に、計算量の上限下限。

その他意識すべきこと

空間計算量

その処理を実行するために必要なメモリの量

償却計算量

起こることが稀であり、一度起こると再度起こるまで時間がかかる処理の計算量

再度起こるまでに計算時間を「償却」できると考える

探索する要素数が半分づつ減っていく場合、O(logN)と推測できる

メモ化

指数時間オーダーの再起アルゴリズムに対して、メモ（キャッシュ）を利用することで、定数時間処理に落ち着ける手法

世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法~