证明O（max {f（n），g（n）} = O（f（n）+ g（n））

Question

我有点困惑于大O符号以及如何证明它最大。我如何用最大值？证明O（max {f（n），g（n）}）= O（f（n）+ g（n））？

Answer 1

假设你的意思是计算f（n）和g（n）最大值的时间复杂度。计算两个数字的最大值是一个常数时间操作*。计算左参数需要O（f（n）），右参数需要O（g（n））。所以O（f（n）+ O（f（n））+ O（g（n））的时间复杂度简化为O（f G（N））。

*注意：最多取两个值是计算机中的恒定时间操作，但计算机不是图灵机。对于大数字来说，确定两个数字的最大值在数字大小上是线性的。

假设你指的是f（n）和g（n）的最大时间复杂度的顺序。然后你使用这样的事实，即由于最大运行时间将是O（f（n））或O（g（n））。由于O（f（n）+ g（n））> O（f（n））和O（f（n）+ g（n））> O（g（n）），出来。这有点便宜，但上限不一定要紧。