計算量ってパッとわからないので勉強

leetcode で再帰アルゴリズムの勉強をしていて、 O(n) とか O(n²-1) とかでてきてもパッと想像できない。
何かがわかってないのだろうけど、なかなかきついのでちゃんと勉強してみた。

せっかく勉強したのでメモっておく。

O(T) は通情再帰呼び出し数と時間の積になる。再帰の回数を R とし再帰呼び出し毎にかかる時間の複雑さ (time complextly of calicuration) は O(s) とすると O(T) = R * O(s) の式で表すことができる。

書いてたらなんとなくわかってきた。

フィボナッチ数列を brute force で計算した時の計算量は binary tree の node の数が再帰の数になるので 2ⁿ -1 回で1つあたりの計算時間は一定だから O(2ⁿ) ということになる。（-1 は計算量として誤差なので省略
以下は実際のコードのタイム

# n = 50
12586269025
go run .  73.30s user 0.35s system 99% cpu 1:13.70 total

メモ化すると計算時間は一定のまま n 回の計算量で住むので O(n) になる。
以下はメモ化時のタイム

# n = 50
12586269025
go run .  0.24s user 0.21s system 100% cpu 0.441 total

なるほど、理解できてきたかも。

メモ化の基本的な動きと計算量の簡単な出し方が学べたので満足。
とか言ってたらまたこんな時間だ...

Whimlog