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

投稿者: | 2015/12/15

アルゴリズム と 方程式

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

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

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

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

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

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です