http://www.iijlab.net/~ew/ptt.html
の最後に載ってるfibがO(log n)でなかったかな