复杂性分析的简化 令TN)为表示算法A的复杂性函数,若存在T(N), 使得 Lim N- (T(N)-T(N/TN)=0 那么,就可以用T(N)来代替T(N),从而简化复杂 性的分析 例如:T(N)=3N2+4NogN+7,T(N)=3N2,则 Lim N- (T(N)-TIN/T(N Lim N-a 4Nlog N+7 /3N2-+4NlogN+7=0 2021/221 计算机算法设计与分析 92021/2/21 计算机算法设计与分析 9 复杂性分析的简化 ◼ 令T(N)为表示算法A的复杂性函数，若存在Ť (N)， 使得 Lim N→ (T(N) – Ť(N)) / T(N) = 0 那么，就可以用Ť(N)来代替T(N) ，从而简化复杂 性的分析。 ◼ 例如：T(N) = 3N2+4NlogN+7，Ť(N) = 3N2 ，则 Lim N→ (T(N) – Ť(N)) / T(N) = Lim N→ 4NlogN+7 / 3N2+4NlogN+7 = 0