フィボナッチ
http://blog.livedoor.jp/dankogai/archives/50958771.html
うーん、本当に任意の自然数nについてfib(n)を求めるのであれば、通常の意味での計算量*1はO(n)未満になるわけがないのですが（自然数mを出力するだけでO(log(m))の時間がかかる）、
- 一定の有限範囲内のnについて、
- fib(n)を定数桁近似して出力する
と問題を変更しているのでしょうか？*2 それはそれで、入力が有限なので、「計算量」の定義が成立しないと思うのですが…
追記：ツッコミだけでは何なので、私はunion-find（の計算量にアッカーマン関数の逆数が出現すること）の直観的説明が知りたいです（←無理）。
追記２：私ごときが首をつっこむことではなかったらしい（はてなブックマークの「このエントリーを含む…」のあたり、特に
- http://d.hatena.ne.jp/maehara/20071201
- http://d.hatena.ne.jp/smoking186/20071130/1196386299
- http://d.hatena.ne.jp/inamori/20071129
などをば）。あと、確かに「186」氏の凡ミスは謎だが（よほど慌てて書いた？…にしても有り得ない勘違い）、いくら何でもこのレベルで「動かさないとわからない」というのは、さすがに（少なくとも186氏に対しては）言いがかりに近いと思う。むしろ（どうせ実行しても有限のケースしかカバーできないので）「動かすだけではわからない」からこそ正確な定義や論証が必要なのだが…
