试题详情
简答题求证：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）}）

  • 关注下方微信公众号，在线模考后查看

热门试题