在渐进分析中等于符号的滥用 我们用f(n)=0(g(n))来表示f(n)是0(g(n)的一个成员函数而 不用传统的T(n)∈0(f(n))来表示。原因？没有原因，习惯问题而 己。 例子 -f(n)=5n3:g(n)=3n2 -f(n)=O(n3)=g(n) butf(n)≠g(n). 。 更好的表式方式：T(n∈O(f(n) -5n3∈0(n3) -3n2 e o(n2)c O(n") 16
16 在渐进分析中等于符号的滥用 我们用f(n)= O(g(n))来表示 f(n) 是 O(g(n))的一个成员函数而 不用传统的T(n)O(f(n))来表示。原因？没有原因，习惯问题而 已。 例子 – f(n) = 5n3; g(n) = 3n2 – f(n) = O(n3) = g(n) – but f(n) g(n). 更好的表式方式: T(n) O(f(n)). – 5n3 O(n3) – 3n2 O(n2) O(n3 )
在渐进分析中等于符号的滥用 因此f(n)=⊙(g(n)的确切意义是：f(n)∈⊙(g(n)。 一般情况下，等式和不等式中的渐近记号⊙(g(n)表示©(g(n)中的 某个函数。 例如：2n2+3n+1=2n2+⊙(n)表示 2n2+3n+1=2n2+f(n),其中f(n)是⊙(n)中某个函数。 等式和不等式中渐近记号O,0,2和ω的意义是类似的。 17
17 在渐进分析中等于符号的滥用 因此f(n)= (g(n))的确切意义是：f(n) (g(n))。 一般情况下，等式和不等式中的渐近记号(g(n))表示(g(n))中的 某个函数。 例如：2n 2 + 3n + 1 = 2n 2 + (n) 表示 2n 2 +3n +1=2n 2 + f(n)，其中f(n) 是(n)中某个函数。 等式和不等式中渐近记号O,o, 和的意义是类似的
渐近分析中函数比较 f(n)=O(g(n)≈a≤b; f(n)=2(g(h)≈a≥b: fn)=⊙(g(n)≈a=b: f(n)=o(g(n)≈a<b; f(n)=o(g(n)≈a>b. 18
18 渐近分析中函数比较 f(n)= O(g(n)) a b; f(n)= (g(n)) a b; f(n)= (g(n)) a = b; f(n)= o(g(n)) a < b; f(n)= (g(n)) a > b
渐近分析记号的若干性质 (1)传递性： f(n)=⊙(g(n),g(n)=⊙(h(n)→fn)=o(h(n): f(n)=O(g(n)),g(n)=O(h(n))f(n)=O(h(n)): f(n)=2(g(n),gn)=2(h(n)→fn)=2(h(n): f(n)=o(g(n)),g(n)=o(h(n))f(n)=o(h(n)): f(n)=o(g(n)),g(n)=@(h(n))f(n)=@(h(n)); 19
19 渐近分析记号的若干性质 （1）传递性： f(n)= (g(n))， g(n)= (h(n)) f(n)= (h(n))； f(n)= O(g(n))， g(n)= O (h(n)) f(n)= O (h(n))； f(n)= (g(n))， g(n)= (h(n)) f(n)= (h(n))； f(n)= o(g(n))， g(n)= o(h(n)) f(n)= o(h(n))； f(n)= (g(n))， g(n)= (h(n)) f(n)= (h(n))；
(2)反身性： f(n)=Θ(f(n): f(n)=O(f(n)): f(n)=2(f(n), (3)对称性： f(n)=(g(n)台g(n)=Θ(f(n), (4)互对称性： f(n)=O(g(n))g(n)=(f(n)); f(n)=o(g(n))g(n)=@(f(n)); 20
20 （2）反身性： f(n)= (f(n))； f(n)= O(f(n))； f(n)= (f(n)). （3）对称性： f(n)= (g(n)) g(n)= (f(n)) . （4）互对称性： f(n)= O(g(n)) g(n)= (f(n)) ； f(n)= o(g(n)) g(n)= (f(n)) ；