実装者のための計算量のはなし - O(logN)などをわかり易く説明しました -

計算量の授業は苦手なものの一つでした。でも、NoSQLのRedisやPythonなどのマニュアルを読んでいると、こんな感じのデータ構造なのか、などとイメージできていました。

とはいえ、苦手な分野だったので若い人には自分で調べる様に言っていたのですが、どうもわかっていない。開発の際は性能試験をするので品質には問題ないのですが、設計する際にきちんとイメージできるのか不安になりました。

私がなぜイメージできるかを考えると、アセンブリ言語の処理時間をクロック数で数えたり、アルゴリズムを学んだりと昔ながらの勉強法で、計算量と実装が結びついていたからだと思いました。

そこで若い人たちに、アルゴリズム＋データ構造と計算量の関係を説明したところ予想外に好評で、ある程度はイメージできる様になった様ですので、スライドを公開します。RDB処理のようになるべくDBMSに任せて遅いところをチューニングすれば良い、といった単純な考えでは不十分である事がわかっていただけると思います。

そして、単に呼び出すメソッドの計算量だけでなく、呼び出す側の計算量も考えないといけない事。アルゴリズム＋データ構造がイメージできれば、こんなメソッドがあるはずだとか、ハッシュの苦手な処理を速くするようにセッターをラップすれば最大値をO(1)で得られる、ということも理解していただけるでしょう。

計算量のはなし from Makoto SAKAI