下限g2 定义 对于非负函数T(n),若存在两个正常数c 称T()在集合9有T(n)>=cm, 和n0,对任意n>n 对于问题的所有输入,只要输入规模足够大 (m>n0,该算法均多于cf(n)步
下限 定义: 对于非负函数 T(n), 若存在两个正常数c 和 n0 ，对任意n > n0，有 T(n) >= cf(n)， 称T(n)在集合 (f(n))中 对于问题的所有输入，只要输入规模足够大 (n>n0 ), 该算法均多于cf(n)步
Q示例 T(m)=c1n2+c27 对于所有的n>1,c1n2+C2n>=C1n 因此对于c=C1和m0=1,有 T(n)>= cn2 根据定义,T(n)在g2(m2)中 同样,我们希望找出最紧(最大的)的下限
示例 T(n) = c1n 2 + c2n. 对于所有的 n > 1, c1n 2 + c2n >= c1n 2 因此对于c = c1 和 n0 = 1，有 T(n) >= cn2 根据定义, T(n)在 (n 2 )中 同样，我们希望找出最紧（最大的）的下限
Q表示法 当上、下限相等时,可用⊙表示法 定义 如果一种算法既在Oh(m)中,又在9(h(m) 中,则称其为⊙(h(m)
表示法 当上、下限相等时，可用 表示法 定义: 如果一种算法既在O(h(n))中，又在(h(n)) 中，则称其为(h(n))
个错误理解 混淆最差情况和上限的概念. 上限指的是增长率 而最差情况是指给定规模时,在所有可能的 输入情况中,最差的那种输入情况
一个错误理解 混淆最差情况和上限的概念. 上限指的是增长率. 而最差情况是指给定规模时，在所有可能的 输入情况中，最差的那种输入情况
化简法贝 1.若fn)在Og(m)中,且g(m)在O(h(m)中 则(n)在O(h()中 2.若f(n)在O(kg(m)中,对于任意常数k>0 成立,则fm)在O(g(m)中 3.若f1(m)在O(g1(m)中,且2()在O(g2(n) 中,则(f1+))在Omax(g1(m),g2(m))中 4.若千1(n)在O(g(m)中,且f2(m)在O(g2(m) 中,则千()2(n)在O(g1(m)g2()中
化简法则 1. 若 f(n) 在O(g(n))中，且 g(n) 在O(h(n))中, 则 f(n) 在O(h(n))中. 2. 若 f(n) 在O(kg(n))中，对于任意常数 k > 0 成立, 则 f(n) 在O(g(n))中. 3. 若 f1 (n) 在O(g1 (n))中，且 f2 (n) 在O(g2 (n)) 中, 则 (f1 + f2 )(n) 在O(max(g1 (n), g2 (n)))中. 4. 若 f1 (n) 在O(g1 (n))中，且 f2 (n) 在O(g2 (n)) 中， 则 f1 (n)f2 (n) 在O(g1 (n)g2 (n))中