ページ 11

和の法則

Posted: 2007年5月19日(土) 20:06
by 大工
アルゴリズムの教科書によくある和の法則 → T1(n)とT2(n)をそれぞれO(f1(n)),O(f2(n))である計算量とする。このとき,T1(n)+T2(n)はO(max(f1(n),f2(n)))である。

この法則にあるmax()がどのような意味をもつのかわかりません。。。。

すみませんが解説お願いします><。。

Re:和の法則

Posted: 2007年5月19日(土) 20:33
by box
全体計算量のオーダーは、部分計算量のオーダーが最大であるものに
等しくなる、という意味ではないでしょうか。

例えば、O(n3)とO(n2)の計算量の和を求めるとすると、
つまるところO(n3)の方が大きく効いてきて、
O(n2)の方は相殺されてしまう、ということではないかと思います。

Re:和の法則

Posted: 2007年5月20日(日) 00:27
by 大工
あ、そっか!

ありがとうございます。