O(n)の処理をちょっとでも高速化したい。 プログラムがいろいろあれば、そのアプローチもいろいろなはず。 とはいえ、高速化といえば、その基本に次の3点があるそうです。
- 処理する数 n をできる限り減らす。
- 処理する数 n が減らせないなら、 1回あたりの処理を軽くする
- 別のアルゴリズムを使って O(n) より小さな傾きの処理に変える
ここでは、2番目の「1回あたりの処理を軽くする」に焦点を当てた高速化について 思いつく限り列挙していこうかと。 …というか、高速化について書かれたサイトの多くは、この点について述べていることが多いと思うけど。。