あれ〜
指名を受けたので記事書こうかと思ったけど, okamoto7先生ので十分だと思ったので止め.
(id:smoking186さん)
えー．
わかりやすさの本質？
もうこの話題関連から抜け出せなくなってるのかも．若干古いところから引いてきますが．
不正確だったり自己流の表現だから悪いという人は、「わかりやすさ」というものの本質を理解していない。「わかりやすさ」とは突き詰めれば「不正確さ」だ。厳密に正しい説明をするとわかりにくいから、あえて不正確に表現して分かりやすくする。
あえて極論っぽく書かれてるのかもしれませんが，「不正確でいる」ことと「端折る」ことは全然違うと思うんです．はい．
それと，不正確な記述をしていることを意識しているかそうでないか，とか，不正確な部分に疑問を抱かれたときにそれを正確にできるかそうでないか，とか，そういうことが重要なのではないかとも思うわけです．はい．もし本当に「あえて不正確に表現している」ならば，ですけど．私も，わかった気にさせることを目的とする場合，そういう手段をよくとります．
それにこうやって突っ込みを皆が入れられる授業こそ、生きた授業ではないかと思う。書いてあることが卒のない説明は退屈なだけだ。そんな解説書は他にいくらでもあるだろう。
突っ込みを皆が入れられる授業は生きた授業だとは思うけども，その方向がネガティブな方向かポジティブな方向かで得られるものはかなり違うと思います．ここでの突っ込みとその応対はネガティブな方向にどんどん向かってるような気がします．
ちなみに私は，書いてある説明に卒がないアルゴリズムの解説書や教科書に出会ったことがないです．残念ながら．
あと，下の方のコメントに書いてある関数云々っていうところは本当にそんな風に高校か大学で習ったんですか？と疑問に思ってしまうところではあるけど，本論とずれるので以上で終了．
結局，計算モデル
やっぱりちょっと書こう．もう逃れられない．
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アルゴリズムの世界では，外部記憶アクセス回数を数えて計算量とすることが多いです．つまり，実世界のコンピュータやシステムの振舞いをどのように記述するのが妥当かということを考えて人々がいろいろなモデルを提案しているからこうなっているわけで，「計算量」というのはモデルに依存する概念なわけです．実はそういうことがアルゴリズムの教科書などにしっかりと書かれていないのは問題だと思っていますが，授業でそういう話に立ち入りすぎるのはかえって混乱を招くでしょう．なので私としては「計算量」ということばを使わないことを提案します．少なくとも，授業をする人が「計算量」ということばのそういう側面を認識する必要はあると思っています．
