计算机问题求解一论题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是 什么“东 西”的规 模？ 这里的最 坏是什么 意思？ 这里的平 均是什么 意思？