最適化のために参考になるアルゴリズム

2015年12月6日

• Karatsuba 法による乗算

  • n 桁の乗算を行うには Ο(n²) の計算量が必要であるが、Karatsuba法では Ο(n^log₂3)で可能
  • http://www.finetune.co.jp/~lyuka/technote/fract/bmul.html

• バケットSort

  • 一般にソートはΟ(nlogn)が必要だが制限付きでΟ(n)で実現する

  • Wiki バケットSort

• Consistent hashing

  • コンシステントハッシュ法 (Consistent hashing) はスロットの追加や削除に対して、最小限のキーのスロットへのマッピングの変更で、ハッシュテーブルの機能を提供することのできる特殊なハッシュ法。

  • http://www.hyuki.com/yukiwiki/wiki.cgi?ConsistentHashing