求证：O（f（n））+O（g（n））=O（max{f（n），g（n）}）。
正确答案:
对于任意f1（n）∈O（f（n）），存在正常数c1和自然数n1，使得对所有n≧n1，有f1（n）≦c1f（n）。
类似地，对于任意g1（n）∈（g（n）），存在正常数c2和自然数n2，使得对所有n≧2，有g1（n）≦c2g（n）
令c3=max{c1，c2}，n3=max{n1，n2}，h（n）=max{f（n），g（n）}。
则对所有的n≧3，有
f1（n）+g1（n）≦c1f（n）+c2g（n）
≦c3f（n）+c3g（n）
=c3（f（n）+g（n））
≦c32max{f（n），g（n）}
=2c3h（n）=O（max{f（n），g（n）}）
类似地，对于任意g1（n）∈（g（n）），存在正常数c2和自然数n2，使得对所有n≧2，有g1（n）≦c2g（n）
令c3=max{c1，c2}，n3=max{n1，n2}，h（n）=max{f（n），g（n）}。
则对所有的n≧3，有
f1（n）+g1（n）≦c1f（n）+c2g（n）
≦c3f（n）+c3g（n）
=c3（f（n）+g（n））
≦c32max{f（n），g（n）}
=2c3h（n）=O（max{f（n），g（n）}）
答案解析:有
微信扫一扫手机做题