计算机问题求解一论题3-3 -摊还分析 2022年09月21日
计算机问题求解 – 论题3-3 - 摊还分析 2022年09月21日
问题1：摊还分析有什么用？
问题1：摊还分析有什么用？
特殊的栈操作会带来不可接受的复杂度吗？ MULTIPOP(S,k) 1 while not STACK-EMPTY(S)and k >0 2 POP(S) 3 k=k-1 认定push和pop操作都是O(1)时，在一个空栈上执行序列 长度为n的push、pop和Multipop操作，时间复杂度如何？ 0(n2)?
特殊的栈操作会带来不可接受的复杂度吗？ 认定push和pop操作都是O(1)时，在一个空栈上执行序列 长度为n的push、pop和Multipop操作，时间复杂度如何？ O(n2 )?
最坏情况下，仍然是O()的！ ·在一个空栈上的n个操作，不可能出现n个multipop操作！ 虽然我们相信不会是0(2)，但是我们仍然要找到 一个科学方法去分析这种情况！ Aggregate、Account、Potential
最坏情况下，仍然是O(n)的！ • 在一个空栈上的n个操作，不可能出现n个multipop操作！ 虽然我们相信不会是O(n2 ),但是我们仍然要找到 一个科学方法去分析这种情况! Aggregate、Account、Potential
Aggregate(聚合)分析 ·聚合分析的基本思想： ·从宏观上观察，找到n个操作的最坏时间开销T(n) ·从微观上看，每个操作的均摊（平均”）开销就是T(n)/n 必生的n是 什么“东 这里的最 这里的平 西”的规 坏是什么 均是什么 模？ 意思？ 意思？
Aggregate(聚合)分析 • 聚合分析的基本思想： • 从宏观上观察，找到n个操作的最坏时间开销T(n) • 从微观上看，每个操作的均摊(“平均”)开销就是T(n)/n 这里的n是 什么“东 西”的规 模？ 这里的最 坏是什么 意思？ 这里的平 均是什么 意思？
从宏观上看（合计）： ·每个元素最多只能被pop一次 ·Pop和nultipop中的pop的次数总和，最多和push次数一样多 ·长度为n的操作序列，最多有n个元素被(push、pop)操作 尽管multipop:是On)的，理论上空栈上的n 个操作最坏情况下是O(n)的。但是，合计的 操作代价仍然是O(n)的！
从宏观上看(合计)： • 每个元素最多只能被pop一次 • Pop和multipop中的pop的次数总和，最多和push次数一样多 • 长度为n的操作序列，最多有n个元素被(push、pop)操作 尽管multipop是O(n)的，理论上空栈上的n 个操作最坏情况下是O(n2 )的。但是，合计的 操作代价仍然是O(n)的！
N个increase操作的代价 Counter Total 一次位翻转：0(1) value cost 0 00000000 0 1 00000001 00000010 3 00000011 4 INCREMENT(A) 4 0000 100 7 5 000 0 101 8 1i=0 6 0 110 10 2 while i A.length and Ai==1 7 0 0 1 8 0 000 15 3 A[]=0 9 0 01001 16 10 00001 010 18 4 i=i+l 11 0000101 5 if i A.length 12 00001100 13 00001101 23 6 A[]=1 14 00001110 2 1 000011 26 16 00010000 31 在A的基础上累加1：Θ(K) K=A.length 将计数器从0累加到16的实际位翻 转次数（代价）
N个increase操作的代价 在A的基础上累加1： Θ(k) 将计数器从0累加到16的实际位翻 转次数(代价) 一次位翻转：O(1) K=A.length
将计数器从0累加到，最坏情况翻转代价？ 从0累加到n,最坏代价： O(kn)? 什么是最坏情况？ 计数经历从(2i)-1递进到2i时
将计数器从0累加到n，最坏情况翻转代价？ 什么是最坏情况？ 计数经历从(2^i)-1递进到2^i时 O(kn)? 从0累加到n，最坏代价：
实际上，一个更紧致的上界是O(n) ·并不是每次递进1，所有的bit都会翻转的！ ·A[O]每次都翻转 ·A[1]每2次翻转一次 ·A[总共翻转了n/2i次 ·合计一下： L」<n∑克 i=0 三 2n. 从宏观上观察，位翻转最多2n次
实际上，一个更紧致的上界是O(n)! • 并不是每次递进1，所有的bit都会翻转的！ • A[0]每次都翻转 • A[1]每2次翻转一次 • A[i]总共翻转了n/2^i次 • 合计一下： 从宏观上观察，位翻转最多2n次
聚合摊还代价 The worst-case time for a sequence of n INCREMENT operations on an initially zero counter is therefore O(n). The average cost of each operation,and therefore the amortized cost per operation,is O(n)/n=O(1). 什么是 aggregate 方法？
聚合摊还代价 • The worst-case time for a sequence of n INCREMENT operations on an initially zero counter is therefore O(n). • The average cost of each operation, and therefore the amortized cost per operation, is O(n)/n=O(1). 什么是 aggregate 方法？