和の法則

[大工]

アルゴリズムの教科書によくある和の法則 → Ｔ１(ｎ)とＴ２(ｎ)をそれぞれＯ(ｆ１(ｎ))，Ｏ(ｆ２(ｎ))である計算量とする。このとき，Ｔ１(ｎ)＋Ｔ２(ｎ)はＯ(ｍａｘ(ｆ１(ｎ)，ｆ２(ｎ)))である。

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

すみませんが解説お願いします＞＜。。

[box]

全体計算量のオーダーは、部分計算量のオーダーが最大であるものに
等しくなる、という意味ではないでしょうか。

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

[大工]

あ、そっか！

ありがとうございます。