渐近分析:大O 定义 对于非负函数T(m),若存在两个正常数c和 0,对任意n>m,有T()<=cf(n),称 T(n)在集合Of(n)中 用法: 某算法的[最佳,平均,最差]情况在O(n2)中 含义为 对于问题的所有[最佳,平均,最差]输入,只要输 人规模足够大(n>no),该算法总能在cf(n)步内完 成
渐近分析：大O 定义: 对于非负函数 T(n), 若存在两个正常数c和 n0 ，对任意n > n0，有 T(n) <= cf(n)，称 T(n)在集合 O(f(n))中 用法: 某算法的 [最佳, 平均, 最差] 情况在 O(n 2 ) 中. 含义为: 对于问题的所有[最佳, 平均, 最差] 输入，只要输 入规模足够大 (n>n0 ), 该算法总能在cf(n)步内完 成
大O(续) 大○表示法描述上限 例:若T(n)=3n2则T(n)在O(m2)中 最紧的上限 虽然T(m)=3m2在O(m3)中,但我们多说在 O(m2)中
大O (续) 大O表示法描述上限. 例: 若 T(n) = 3n 2 则 T(n) 在 O(n 2 )中. 最紧的上限: 虽然 T(n) = 3n 2 在 O(n 3 )中, 但我们多说在 O(n 2 )中
大O示例 例1:在数组中找值(平均情况) T(n=csn/2 对于所有的n>1,c/2<=c。m 根据定义,T(m)在O(m)中,m=1,c=cs
大O 示 例 例 1: 在数组中找值 X (平均情况). T(n) = csn/2. 对于所有的 n > 1, csn/2 <= csn. 根据定义, T(n)在 O(n) 中， n0 = 1 ，c = cs
大O示例(续) 例2:T(m)=c1n2+c2n(平均情况) 对于所有的n>1, c1n2+c2<=c1n2+c2n2<=(c1+c2)n2 T()<=cn2,(c=c1+C2,mo=1) 因此,T(n)在O(m2)中 例3:T(n)=C.此时说在O(1)中
大O 示 例（续） 例 2: T(n) = c1n 2 + c2n （平均情况）. 对于所有的n > 1 ， c1n 2 + c2n <= c1n 2 + c2n 2 <= (c1 + c2 )n 2 . T(n) <= cn2 ， （c = c1 + c2 ， n0 = 1）. 因此, T(n)在 O(n 2 ) 中. 例 3: T(n) = c. 此时说在 O(1)中
通常的错误理解 错误说法: “我的算法的最佳情况是n=1,因为这时 算法运行时间最短.” 最佳情况是指对于所有的输入规模为η的情况, 资源耗费(时间)最少的那种情况 而大O则是指n趋向∞时的增长率
通常的错误理解 错误说法： “我的算法的最佳情况是 n=1 ，因为这时 算法运行时间最短.” 最佳情况是指对于所有的输入规模为n的情况， 资源耗费（时间）最少的那种情况 而大O则是指n趋向时的增长率