二排序与顺序统计 6 主要适用范围：Tm)=aT(m/)+fm,其中a≥1，b>1,f渐近非负。 主定理[The master theorem]):若fn)=O(nioga-c),e>0,则T(n)=0(nloa):若f(n)= 0(ma1og,则T(m)=6(noa1og+1n:若fm）=2(mlo8-),e>0,且af(n/)≤cf(m) 则T(m)=6(fm) *种情况存在间隙，可能无法判断（如T(m)=3T(n/3)+1og1ogn),并不代表递归方程无解 S1.5摊还分析 思路：考虑一系列操作的可能的最坏情况的平均复杂度为 *不涉及概率问题，与平均复杂度分析不同 例：栈操作 只有PUSH和POP时，视二者代价为1，则操作的平均代价必然为1。 在PUSH和POP上增添一个MULTIPOP(k),一次允许弹出多个元素（最多到栈底），其代价实际上为 min(s,k),其中s代表栈中元素。 *加入此操作后，n次操作的平均代价？ 虽然MULTIPOP的上限代价为Om,但由于最多入栈n次，出栈也最多n次，实际上平均代价仍为 0(1). 例：二进制计数器 k位二进制计数器，将每位的修改作为代价1。在允许加法时，一次加法最高需要修政k位，但是n次 的总代价可以估算为号+2婴+3爱+·=0()，于是平均代价仍为0(1)。 核算法[accounting method] 给每个操作赋予摊还代价，保证每次操作摊还代价的总和不小于实际代价（而当某步摊还代价比实际代价 大时，将其称为信用，用来支付之后的差额)。 *栈操作的例子中，PUSH的摊还代价为2，其余全为：对二进制计数器，假设日到1操作【置位] 的摊还代价为2,1到日操作[复位]的摊还代价为©，由于每次增加恰好产生一次置位，而复位时每 个为1的位都保留信用支付，因此可得到结论。 势能法[potential method] 对每个状态定义势函数[映射到实数]，一般初始状态为日。将摊还代价定义为代价+操作后的势-操作 前的势。 *栈操作的例子中，势为栈中元素个数：对二进制计数器，势为数中1的个数。可发现得到的摊还代价与 核算法中一致。 *通过势能法分析，当二进制计数器计数器不是从零开始时，这样的定义仍然合理，于是个操作的实际 代价为2n+bn-如，b为势函数。于是，充分大时平均复杂度仍然(1)。 二 排序与顺序统计 一些概念 稳定性：不论输入数据如何分布，关健字相同的数据对象（如两个3）在整个过程中保持相对位置不变 内排序/外排序：是/否在内存中进行 时间开销：通过比较次数与移动次数衡量 评价标准：所需时间[主要因素]、附加空间[一般都不大，矛盾不突出]、实现复杂程度 二 排序与顺序统计 8 主要适用范围：T(n) = aT(n/b) + f(n)，其中 a ≥ 1, b > 1，f 渐近非负。 主定理 [The master theorem]：若 f(n) = O(n logb a−ε ), ε > 0，则 T(n) = Θ(n logb a )；若 f(n) = O(n logb a logk n)，则 T(n) = Θ(n logb a logk+1 n)；若 f(n) = Ω(n logb a−ε ), ε > 0，且 af(n/b) ≤ cf(n)， 则 T(n) = Θ(f(n))。 *三种情况存在间隙，可能无法判断 (如 T(n) = 3T(n/3) + log log2 n)，并不代表递归方程无解 §1.5 摊还分析 思路：考虑一系列操作的可能的最坏情况的平均复杂度为 *不涉及概率问题，与平均复杂度分析不同 例：栈操作 只有 PUSH 和 POP 时，视二者代价为 1，则操作的平均代价必然为 1。 在 PUSH 和 POP 上增添一个 MULTIPOP(k)，一次允许弹出多个元素 (最多到栈底)，其代价实际上为 min(s,k)，其中 s 代表栈中元素。 *加入此操作后，n 次操作的平均代价？ 虽然 MULTIPOP 的上限代价为 O(n)，但由于最多入栈 n 次，出栈也最多 n 次，实际上平均代价仍为 O(1)。 例：二进制计数器 k 位二进制计数器，将每位的修改作为代价 1。在允许加法时，一次加法最高需要修改 k 位，但是 n 次 的总代价可以估算为 n 2 + 2 n 4 + 3 n 8 + · · · = O(n)，于是平均代价仍为 O(1)。 核算法 [accounting method] 给每个操作赋予摊还代价，保证每次操作摊还代价的总和不小于实际代价 (而当某步摊还代价比实际代价 大时，将其称为信用，用来支付之后的差额)。 *栈操作的例子中，PUSH 的摊还代价为 2，其余全为 0；对二进制计数器，假设 0 到 1 操作 [置位] 的摊还代价为 2，1 到 0 操作 [复位] 的摊还代价为 0，由于每次增加恰好产生一次置位，而复位时每 个为 1 的位都保留信用支付，因此可得到结论。 势能法 [potential method] 对每个状态定义势函数 [映射到实数]，一般初始状态为 0。将摊还代价定义为代价 + 操作后的势‐操作 前的势。 *栈操作的例子中，势为栈中元素个数；对二进制计数器，势为数中 1 的个数。可发现得到的摊还代价与 核算法中一致。 *通过势能法分析，当二进制计数器计数器不是从零开始时，这样的定义仍然合理，于是 n 个操作的实际 代价为 2n + bn − b0，b 为势函数。于是，充分大时平均复杂度仍然 O(1)。 二 排序与顺序统计 一些概念 稳定性：不论输入数据如何分布，关键字相同的数据对象 (如两个 3) 在整个过程中保持相对位置不变 内排序/外排序：是/否在内存中进行 时间开销：通过比较次数与移动次数衡量 评价标准：所需时间 [主要因素]、附加空间 [一般都不大，矛盾不突出]、实现复杂程度