最坏、最好或平均的情况 ■令:D为规模为N的合法输入的集合; I*表示在最坏情况下的输入; Ⅳ表示在最好情况下的输入; P①输入I出现的概率 W(N=max(N,D=t(N,I) B(N-min edt(N,D=t(N, I) ■A(N)=∑lepP(I)T(N,I 三者中最常用的是W(N)。 2021/221 计算机算法设计与分析2021/2/21 计算机算法设计与分析 8 最坏、最好或平均的情况 ◼ 令：D为规模为N的合法输入的集合； I*表示在最坏情况下的输入； I #表示在最好情况下的输入； P(I)输入I出现的概率。 ◼ W(N) = max IDT(N, I) = T(N, I*) ◼ B(N) = min IDT(N, I) = T(N, I# ) ◼ A(N) =  IDP(I)T(N, I) ◼ 三者中最常用的是W(N)