結局，計算モデル

やっぱりちょっと書こう．もう逃れられない．

2数同士の演算を考えるときはビットモデルでしょうか．なので，ビット同士の操作 (AND, OR, XOR，NOTなど) の回数を計算の単位と考えるのが普通でしょうか．n桁の2数の和を求める計算量がO(n)とかいう言い方はこのモデルでの話だと思います．
2数同士の四則演算ぐらいはブラックボックスとして使えるとして普通にアルゴリズムを考える場合はword RAMを考える場合が多いでしょうか．ただし，word長は任意の定数．この「任意の定数」が実は重要だけど，word長を気にする計算量評価モデルもあり．普通は1ワード同士の演算は1単位と見なすので，第nフィボナッチ数を求めるための計算量がO(log n)という言い方も許せるはずです．
計算幾何の場合はreal RAMをモデルとすることが多いでしょうか．平面上のn個の点の中のclosest pairを見つけるための計算量がO(n log n)というのはこのモデルでの話です．(そもそも，そうでなければ，2点間の距離を比べることすらままならない．) 最近Timothy ChanとかMihai PatrascuとかErik Demaineとかがword RAMモデルで計算幾何をやる研究をしてて，これはこれで面白いですね．
整列問題や選択問題に対しては，比較モデルを使うことが多いのでしょうか．たとえば「マージソートの計算量がO(n log n)」といってるものの実態は大体比較回数を考えているわけです．基数ソートはビットモデルなんでしょうね．よく分かりませんが．
そのほか，cell probeモデルとかpointer machineモデルとかいろいろありますね．論理回路も計算モデルの1つですね．

ということで，どういう計算モデルを使って，何を計算の単位と考えるかで「計算量」は大きく変わってきます．External memoryアルゴリズムの世界では，外部記憶アクセス回数を数えて計算量とすることが多いです．つまり，実世界のコンピュータやシステムの振舞いをどのように記述するのが妥当かということを考えて人々がいろいろなモデルを提案しているからこうなっているわけで，「計算量」というのはモデルに依存する概念なわけです．実はそういうことがアルゴリズムの教科書などにしっかりと書かれていないのは問題だと思っていますが，授業でそういう話に立ち入りすぎるのはかえって混乱を招くでしょう．なので私としては「計算量」ということばを使わないことを提案します．少なくとも，授業をする人が「計算量」ということばのそういう側面を認識する必要はあると思っています．