アルゴリズムに対するコスト評価

たとえば、1からnまでの数を全て足し算しろと言われて、どういうプログラムを書く?
　r=0;
　for(i=1;iもちろんアルゴリズムの最適化を忘れてはならないよ

加算や比較のコストがO(1)程度として、上のアルゴリズム*1のコストはn*(i加算＋ループ終了判定＋r加算)だけかかり、O(n)。
それに対して、下のアルゴリズムは掛算のコストは高々O(log(n))*2なので、コストはO(log(n))。
注意して欲しいのは、nが少ない場合の評価ではないこと、そして「/2」のコストは何も考慮しないということ。何故かというと、そんなのはほとんど関係ないから。

だって

この前の仕事。4コアのCPUに10GBのメモリを積んだサーバに対して、何ユーザが接続すると思います？答えはユニークユーザで50人、同時接続でも10人がいいところ。贅沢な環境ですよね。n<1000程度なら1μ秒もかからない。どっちのアルゴリズムにしても。
こんな環境だから、上記2つのアルゴリズム程度ならどちらを選んでも影響がなかったり、ましてや「/2」のコストなど全く気にする必要も無い。逆に言えばそんなコストを気にしなくてもいいように、贅沢な環境を用意しているわけで。「/2」の最適化に悩んでたら、もう怒られちゃいます。
といっても、流石に上の2つのアルゴリズムはnが大きくなると性能差が出てくる。そこで、「取り敢えず上のアルゴリズムで組んでみて、後で直す」というのも十分にアリだと思う。上の計算なら既に計算式が公知なんだけど、例えば累乗計算の場合、累積計算位効率的な、公知なアルゴリズムはない（はず）。実際の業務だとそんな場合の方が多いし、高効率より取り敢えず動くものを優先する場面って結構多いです。で、システムが一通り出来上がってからこの部分が目立って遅ければ効率化する、と。

ついでに、効率性と保守性

下のアルゴリズムは一見して累積計算はしていないけど、この程度なら直上にコメント入れるだけで保守性は十分だし、さらに（というか普通は）ライブラリなりに切り出して、getCombination(int n)とかでカプセル化、機能と実装の分離を進めれば、効率性も保守性も十分に両立できる。事後のチューニングにも対応しやすいし。
こんな普通の方法で最適化と保守性、十分両立できません？もちろん、ライブラリのロードコストは無視ですよ。

まとめ

• ほとんどの場合、SI屋のプログラム技術不足はハードウェアで補えます。
• マシン語から高級言語への歴史はプログラムの抽象化の歴史です。具象の世界で考えられる事・考えられない事もあれば、抽象の世界で考えられる事・考えられない事もあるだろうと思います。
• SI屋とWEB屋、ゲーム屋、そして組込屋。それぞれに色んな事情がありそうです。

*1:ループ終了条件はi<=nが正解じゃないかと思われますがー。

*2:素朴に考えても、nはlog(n)ビット（底は2として）で、log(n)ビット掛算はlog(n)*定数回+α程度の加算で実現可能なので。最近のCPUでは加算と同じくらいで云々という記述もあるし、実際どうしてるんだろ。