日刊 あおのうま Vol.1722（2015.12.15）【計算量】

アルゴリズム と 方程式

社内勉強会で出たちょっとした問題。
次の三次方程式を解くプログラムを考えてみようというものだったのですが…。

x^3 + x^2 + x = 1 を満たすx を求めよ。（再近似値 = 0.000001）

パッと考えついたのは力任せな線形探索。
計算量はO(N)

でも、ちょっと考えて二分探索を使えば、計算量はグッと減ってO(log N)になったんですよね。

しかもこれ、以前もやった事があって、前回も同じく線形探索で済ませた記憶が…。
成長無いな私。orz