按照符号O的定义，证明其の运算规则：

①O(f(n))+O(g(n)) = O(max{f(n),g(n)})

②O(f(n))+O(g(n)) = O(f+g)

③O(f)+O(g) = O(fg)

O(f(n))+O(g(n)) = O(max{f(n),g(n)})

证明：

设f(N)和g（N）是定义在正数集上的正函数

设F(N)= Ο(f)

根据记号Ο的定义，存在正常数C₁和自然数N₁，使得对所有的N≥N₁，有F(N)≤C₁ f(N)。

类似地，设G(N)=Ο(g)，则存在正的常数C₂和自然数N₂使得对所有的N≥N₂有G(N)≤C₂g(N)

令：C₃=max(C₁, C₂) N₃=max(N₁, N₂)

和对任意的非负整数N，h(N)=max(f,g),

则对所有的N≥N₃有：

F(N)≤C₁f(N)≤C₁h(N)≤C₃h(N)

类似地，有：

G(N)≤C₂g(N)≤C₂h(N)≤C₃h(N)

因而

Ο(f)+Ο(g) =F(N)+G(N)≤C₃h(N)+ C₃h(N)

=2C₃h(N)

=Ο(h)

=Ο(max(f,g))

转载： http://hi.baidu.com/�����ltl/blog/item/e1375710ff9ccbc0c3fd78fc.html