忘记了密码?新用户?<一个href="//www.parkandroid.com/account/signup/?signup=true&next=/wiki/amortized-analysis/" id="problem-signup-link-alternative" class="btn-link ax-click" data-ax-id="clicked_signup_from_generic_modal" data-ax-type="button" data-next="/wiki/amortized-analysis/">报名
现有的用户?<一个href="//www.parkandroid.com/account/login/?next=/wiki/amortized-analysis/" id="problem-login-link-alternative" class="btn-link ax-click" data-ax-id="clicked_login_from_generic_modal" data-ax-type="button" data-is_modal="true" data-next="/wiki/amortized-analysis/">登录
已经有账户了?<一个href="//www.parkandroid.com/account/login/?next=/wiki/amortized-analysis/" class="ax-click" data-ax-id="clicked_signup_modal_login" data-ax-type="link">日志在这里。
平摊分析是一种分析与数据结构相关的成本的方法,它可以将最差的操作随着时间的推移平均出来。通常,一个数据结构有一个特别昂贵的操作,但它不经常执行。这个数据结构不应该仅仅因为很少执行的一个操作代价高而被标记为代价高的结构。 平摊分析是用来在最坏情况下平均成本高的操作。从成本的角度来看,数据结构的最坏情况是操作的最坏顺序。一旦找到排序,就可以对操作进行平均。 摊销分析主要有三种类型:汇总分析、会计方法和潜在方法。
平摊分析是用来在最坏情况下平均成本高的操作。从成本的角度来看,数据结构的最坏情况是操作的最坏顺序。一旦找到排序,就可以对操作进行平均。 摊销分析主要有三种类型:汇总分析、会计方法和潜在方法。
摊销分析主要有三种类型:汇总分析、会计方法和潜在方法。
平摊分析是什么以及为什么要使用它,这是很重要的。本质上,它归结为对数据结构的“公平”。如果操作相对不常见,那么一个错误的操作不应该破坏数据结构。更确切地说,我们想要了解数据结构在实践中实际是如何执行的,而平摊分析通过为我们提供数据结构随时间变化的准确描述来帮助我们做到这一点。简单地看每个操作最坏情况下的性能可能过于悲观,而平摊分析可以让我们更清楚地了解发生了什么。 假设你想为糕饼义卖做一个蛋糕。蛋糕制作相当复杂,但基本上有两个主要步骤: 把面糊(快)。 在烤箱里烤(慢一点,一次只能放进一个蛋糕)。 与烘烤相比,搅拌面糊花的时间相对较少。之后,你会反思制作蛋糕的过程。当决定是慢、中还是快时,您选择中,因为您将这两种操作(慢和快)进行平均,从而得到中。 现在假设你想做100个蛋糕。要烘焙100个蛋糕,你有两种选择。你可以混合面糊做一个蛋糕,烤它,然后重复。或者,你可以把所有100个蛋糕的面糊混合在一起,然后一个接一个地烘焙。这些方法是慢的、中等的还是快的? 平摊分析告诉我们这两种方法都应该被描述为“中等”,即使你可能要连续烘焙100个蛋糕.即使您可能需要连续处理100个慢操作,但在它们之前有100个快速操作,因此平均值仍然是中等。 最坏的情况意味着不可能想象出更糟糕的事件序列。举个例子来说,跳过搅拌面糊的操作,简单地烤100个蛋糕是没有任何意义的。这将是一个缓慢的烘焙过程,但它没有任何意义,所以不值得分析。蛋糕烘焙过程是一个中间过程,因为混合蛋糕糊和烘焙蛋糕有一个不可逆转的逻辑顺序。
假设你想为糕饼义卖做一个蛋糕。蛋糕制作相当复杂,但基本上有两个主要步骤: 把面糊(快)。 在烤箱里烤(慢一点,一次只能放进一个蛋糕)。 与烘烤相比,搅拌面糊花的时间相对较少。之后,你会反思制作蛋糕的过程。当决定是慢、中还是快时,您选择中,因为您将这两种操作(慢和快)进行平均,从而得到中。 现在假设你想做100个蛋糕。要烘焙100个蛋糕,你有两种选择。你可以混合面糊做一个蛋糕,烤它,然后重复。或者,你可以把所有100个蛋糕的面糊混合在一起,然后一个接一个地烘焙。这些方法是慢的、中等的还是快的? 平摊分析告诉我们这两种方法都应该被描述为“中等”,即使你可能要连续烘焙100个蛋糕.即使您可能需要连续处理100个慢操作,但在它们之前有100个快速操作,因此平均值仍然是中等。
与烘烤相比,搅拌面糊花的时间相对较少。之后,你会反思制作蛋糕的过程。当决定是慢、中还是快时,您选择中,因为您将这两种操作(慢和快)进行平均,从而得到中。 现在假设你想做100个蛋糕。要烘焙100个蛋糕,你有两种选择。你可以混合面糊做一个蛋糕,烤它,然后重复。或者,你可以把所有100个蛋糕的面糊混合在一起,然后一个接一个地烘焙。这些方法是慢的、中等的还是快的? 平摊分析告诉我们这两种方法都应该被描述为“中等”,即使你可能要连续烘焙100个蛋糕.即使您可能需要连续处理100个慢操作,但在它们之前有100个快速操作,因此平均值仍然是中等。
现在假设你想做100个蛋糕。要烘焙100个蛋糕,你有两种选择。你可以混合面糊做一个蛋糕,烤它,然后重复。或者,你可以把所有100个蛋糕的面糊混合在一起,然后一个接一个地烘焙。这些方法是慢的、中等的还是快的? 平摊分析告诉我们这两种方法都应该被描述为“中等”,即使你可能要连续烘焙100个蛋糕.即使您可能需要连续处理100个慢操作,但在它们之前有100个快速操作,因此平均值仍然是中等。
平摊分析告诉我们这两种方法都应该被描述为“中等”,即使你可能要连续烘焙100个蛋糕.即使您可能需要连续处理100个慢操作,但在它们之前有100个快速操作,因此平均值仍然是中等。
最坏的情况意味着不可能想象出更糟糕的事件序列。举个例子来说,跳过搅拌面糊的操作,简单地烤100个蛋糕是没有任何意义的。这将是一个缓慢的烘焙过程,但它没有任何意义,所以不值得分析。蛋糕烘焙过程是一个中间过程,因为混合蛋糕糊和烘焙蛋糕有一个不可逆转的逻辑顺序。
在综合分析中,有两个步骤。首先,我们必须证明一个序列<年代pan class="katex"> n n n业务需要<年代pan class="katex"> T ( n ) T (n) T(n)在最坏的情况下是时间。然后,我们展示每个操作需要的<年代pan class="katex"> T ( n ) n n \压裂{T (n)} nT(n)时间,平均。因此,在综合分析中,每次操作的成本是相同的。在<一个t一个rget="_blank" rel="nofollow" href="#intuition">以前的举个蛋糕制作的例子,这两种操作都被描述为中等,而不是快和慢。 聚合分析的一个常见示例是修改后的<一个href="//www.parkandroid.com/wiki/stacks/" class="wiki_link" title="堆栈gydF4y2Ba" target="_blank">堆栈.堆栈是一个<一个href="//www.parkandroid.com/wiki/linear-data-structures/" class="wiki_link" title="线性数据结构gydF4y2Ba" target="_blank">线性数据结构有两个常数时间的运算。push(元素)将一个元素放在堆栈的顶部,然后pop ()从堆栈中取出顶部元素并返回它。这些操作都是常数时间,所以总共<年代pan class="katex"> n n n操作(任何顺序)将导致<年代pan class="katex"> O ( n ) O (n) O(n)总时间。 现在,一个新的操作被添加到堆栈中。multipop (k)是否会弹出顶部<年代pan class="katex"> k k k或者,如果它在此之前耗尽了所有的元素,它将弹出堆栈中的所有元素并停止。的伪代码multipop (k)看起来像这样: 1 2 3 4 Multipop (k): while stack not empty and k > 0: k = k - 1 看看伪代码,很容易看出这不是一个固定时间的操作。multipop最多能跑多久<年代pan class="katex"> n n n次,<年代pan class="katex"> n n n为堆栈的大小。所以,最坏情况的运行时multipop是<年代pan class="katex"> O ( n ) O (n) O(n).在非典型分析中,这意味着<年代pan class="katex"> n n nmultipop业务需要<年代pan class="katex"> O ( n 2 ) 大(n ^ 2 O \ \大) O(n2)时间。 然而,事实并非如此。思考multipop以及它实际在做什么。multipop除非有一个推入堆栈,否则无法工作,因为它没有什么可以弹出。事实上,任何序列<年代pan class="katex"> n n n的操作multipop,流行和推最多只能接受<年代pan class="katex"> O ( n ) O (n) O(n)时间。multipop,该堆栈中唯一的非常量时间操作,只能执行<年代pan class="katex"> O ( n ) O (n) O(n)时间如果也有过<年代pan class="katex"> n n n是常量时间的推栈上的操作。在最坏的情况下,有<年代pan class="katex"> n n n常数时间的操作,只需要一个操作<年代pan class="katex"> O ( n ) O (n) O(n)时间。 对于任意值<年代pan class="katex"> n n n,任意序列multipop,流行,推需要<年代pan class="katex"> O ( n ) O (n) O(n)时间。所以,通过综合分析, T ( n ) n = O ( n ) n = O ( 1 ) . \frac{T(n)}{n} = \frac{O(n)}{n} = O(1)。 nT(n)=nO(n)=O(1). 所以,这个堆栈的平摊代价是<年代pan class="katex"> O ( 1 ) O (1) O(1)每个操作。
聚合分析的一个常见示例是修改后的<一个href="//www.parkandroid.com/wiki/stacks/" class="wiki_link" title="堆栈gydF4y2Ba" target="_blank">堆栈.堆栈是一个<一个href="//www.parkandroid.com/wiki/linear-data-structures/" class="wiki_link" title="线性数据结构gydF4y2Ba" target="_blank">线性数据结构有两个常数时间的运算。push(元素)将一个元素放在堆栈的顶部,然后pop ()从堆栈中取出顶部元素并返回它。这些操作都是常数时间,所以总共<年代pan class="katex"> n n n操作(任何顺序)将导致<年代pan class="katex"> O ( n ) O (n) O(n)总时间。 现在,一个新的操作被添加到堆栈中。multipop (k)是否会弹出顶部<年代pan class="katex"> k k k或者,如果它在此之前耗尽了所有的元素,它将弹出堆栈中的所有元素并停止。的伪代码multipop (k)看起来像这样: 1 2 3 4 Multipop (k): while stack not empty and k > 0: k = k - 1 看看伪代码,很容易看出这不是一个固定时间的操作。multipop最多能跑多久<年代pan class="katex"> n n n次,<年代pan class="katex"> n n n为堆栈的大小。所以,最坏情况的运行时multipop是<年代pan class="katex"> O ( n ) O (n) O(n).在非典型分析中,这意味着<年代pan class="katex"> n n nmultipop业务需要<年代pan class="katex"> O ( n 2 ) 大(n ^ 2 O \ \大) O(n2)时间。 然而,事实并非如此。思考multipop以及它实际在做什么。multipop除非有一个推入堆栈,否则无法工作,因为它没有什么可以弹出。事实上,任何序列<年代pan class="katex"> n n n的操作multipop,流行和推最多只能接受<年代pan class="katex"> O ( n ) O (n) O(n)时间。multipop,该堆栈中唯一的非常量时间操作,只能执行<年代pan class="katex"> O ( n ) O (n) O(n)时间如果也有过<年代pan class="katex"> n n n是常量时间的推栈上的操作。在最坏的情况下,有<年代pan class="katex"> n n n常数时间的操作,只需要一个操作<年代pan class="katex"> O ( n ) O (n) O(n)时间。 对于任意值<年代pan class="katex"> n n n,任意序列multipop,流行,推需要<年代pan class="katex"> O ( n ) O (n) O(n)时间。所以,通过综合分析, T ( n ) n = O ( n ) n = O ( 1 ) . \frac{T(n)}{n} = \frac{O(n)}{n} = O(1)。 nT(n)=nO(n)=O(1). 所以,这个堆栈的平摊代价是<年代pan class="katex"> O ( 1 ) O (1) O(1)每个操作。
现在,一个新的操作被添加到堆栈中。multipop (k)是否会弹出顶部<年代pan class="katex"> k k k或者,如果它在此之前耗尽了所有的元素,它将弹出堆栈中的所有元素并停止。的伪代码multipop (k)看起来像这样: 1 2 3 4 Multipop (k): while stack not empty and k > 0: k = k - 1 看看伪代码,很容易看出这不是一个固定时间的操作。multipop最多能跑多久<年代pan class="katex"> n n n次,<年代pan class="katex"> n n n为堆栈的大小。所以,最坏情况的运行时multipop是<年代pan class="katex"> O ( n ) O (n) O(n).在非典型分析中,这意味着<年代pan class="katex"> n n nmultipop业务需要<年代pan class="katex"> O ( n 2 ) 大(n ^ 2 O \ \大) O(n2)时间。 然而,事实并非如此。思考multipop以及它实际在做什么。multipop除非有一个推入堆栈,否则无法工作,因为它没有什么可以弹出。事实上,任何序列<年代pan class="katex"> n n n的操作multipop,流行和推最多只能接受<年代pan class="katex"> O ( n ) O (n) O(n)时间。multipop,该堆栈中唯一的非常量时间操作,只能执行<年代pan class="katex"> O ( n ) O (n) O(n)时间如果也有过<年代pan class="katex"> n n n是常量时间的推栈上的操作。在最坏的情况下,有<年代pan class="katex"> n n n常数时间的操作,只需要一个操作<年代pan class="katex"> O ( n ) O (n) O(n)时间。 对于任意值<年代pan class="katex"> n n n,任意序列multipop,流行,推需要<年代pan class="katex"> O ( n ) O (n) O(n)时间。所以,通过综合分析, T ( n ) n = O ( n ) n = O ( 1 ) . \frac{T(n)}{n} = \frac{O(n)}{n} = O(1)。 nT(n)=nO(n)=O(1). 所以,这个堆栈的平摊代价是<年代pan class="katex"> O ( 1 ) O (1) O(1)每个操作。
1 2 3 4
Multipop (k): while stack not empty and k > 0: k = k - 1
看看伪代码,很容易看出这不是一个固定时间的操作。multipop最多能跑多久<年代pan class="katex"> n n n次,<年代pan class="katex"> n n n为堆栈的大小。所以,最坏情况的运行时multipop是<年代pan class="katex"> O ( n ) O (n) O(n).在非典型分析中,这意味着<年代pan class="katex"> n n nmultipop业务需要<年代pan class="katex"> O ( n 2 ) 大(n ^ 2 O \ \大) O(n2)时间。 然而,事实并非如此。思考multipop以及它实际在做什么。multipop除非有一个推入堆栈,否则无法工作,因为它没有什么可以弹出。事实上,任何序列<年代pan class="katex"> n n n的操作multipop,流行和推最多只能接受<年代pan class="katex"> O ( n ) O (n) O(n)时间。multipop,该堆栈中唯一的非常量时间操作,只能执行<年代pan class="katex"> O ( n ) O (n) O(n)时间如果也有过<年代pan class="katex"> n n n是常量时间的推栈上的操作。在最坏的情况下,有<年代pan class="katex"> n n n常数时间的操作,只需要一个操作<年代pan class="katex"> O ( n ) O (n) O(n)时间。 对于任意值<年代pan class="katex"> n n n,任意序列multipop,流行,推需要<年代pan class="katex"> O ( n ) O (n) O(n)时间。所以,通过综合分析, T ( n ) n = O ( n ) n = O ( 1 ) . \frac{T(n)}{n} = \frac{O(n)}{n} = O(1)。 nT(n)=nO(n)=O(1). 所以,这个堆栈的平摊代价是<年代pan class="katex"> O ( 1 ) O (1) O(1)每个操作。
multipop业务需要<年代pan class="katex"> O ( n 2 ) 大(n ^ 2 O \ \大) O(n2)时间。 然而,事实并非如此。思考multipop以及它实际在做什么。multipop除非有一个推入堆栈,否则无法工作,因为它没有什么可以弹出。事实上,任何序列<年代pan class="katex"> n n n的操作multipop,流行和推最多只能接受<年代pan class="katex"> O ( n ) O (n) O(n)时间。multipop,该堆栈中唯一的非常量时间操作,只能执行<年代pan class="katex"> O ( n ) O (n) O(n)时间如果也有过<年代pan class="katex"> n n n是常量时间的推栈上的操作。在最坏的情况下,有<年代pan class="katex"> n n n常数时间的操作,只需要一个操作<年代pan class="katex"> O ( n ) O (n) O(n)时间。 对于任意值<年代pan class="katex"> n n n,任意序列multipop,流行,推需要<年代pan class="katex"> O ( n ) O (n) O(n)时间。所以,通过综合分析, T ( n ) n = O ( n ) n = O ( 1 ) . \frac{T(n)}{n} = \frac{O(n)}{n} = O(1)。 nT(n)=nO(n)=O(1). 所以,这个堆栈的平摊代价是<年代pan class="katex"> O ( 1 ) O (1) O(1)每个操作。
然而,事实并非如此。思考multipop以及它实际在做什么。multipop除非有一个推入堆栈,否则无法工作,因为它没有什么可以弹出。事实上,任何序列<年代pan class="katex"> n n n的操作multipop,流行和推最多只能接受<年代pan class="katex"> O ( n ) O (n) O(n)时间。multipop,该堆栈中唯一的非常量时间操作,只能执行<年代pan class="katex"> O ( n ) O (n) O(n)时间如果也有过<年代pan class="katex"> n n n是常量时间的推栈上的操作。在最坏的情况下,有<年代pan class="katex"> n n n常数时间的操作,只需要一个操作<年代pan class="katex"> O ( n ) O (n) O(n)时间。 对于任意值<年代pan class="katex"> n n n,任意序列multipop,流行,推需要<年代pan class="katex"> O ( n ) O (n) O(n)时间。所以,通过综合分析, T ( n ) n = O ( n ) n = O ( 1 ) . \frac{T(n)}{n} = \frac{O(n)}{n} = O(1)。 nT(n)=nO(n)=O(1). 所以,这个堆栈的平摊代价是<年代pan class="katex"> O ( 1 ) O (1) O(1)每个操作。
对于任意值<年代pan class="katex"> n n n,任意序列multipop,流行,推需要<年代pan class="katex"> O ( n ) O (n) O(n)时间。所以,通过综合分析, T ( n ) n = O ( n ) n = O ( 1 ) . \frac{T(n)}{n} = \frac{O(n)}{n} = O(1)。 nT(n)=nO(n)=O(1). 所以,这个堆栈的平摊代价是<年代pan class="katex"> O ( 1 ) O (1) O(1)每个操作。
T ( n ) n = O ( n ) n = O ( 1 ) . \frac{T(n)}{n} = \frac{O(n)}{n} = O(1)。 nT(n)=nO(n)=O(1).
所以,这个堆栈的平摊代价是<年代pan class="katex"> O ( 1 ) O (1) O(1)每个操作。
这种会计方法的名称很恰当,因为它借鉴了会计的思想和术语。在这里,每个操作都被分配一个费用,称为<年代trong>摊余成本.有些手术的收费可能比实际成本高或低。如果一个操作的平摊代价超过它的实际代价,我们将其差值赋值为a<年代trong>信贷,发送给数据结构中的特定对象。信贷以后可以用来帮助支付其他摊销成本低于实际成本的业务。在任何操作序列中,信用都不可能是负的。 一项业务的摊销成本是在业务的实际成本和存入或用完的信贷之间进行分配。每个操作可以有不同的平摊成本,不像<一个t一个rget="_blank" rel="nofollow" href="#aggregate-analysis">聚合分析.为每个操作选择平摊代价是很重要的,但是对于一个给定的操作,无论操作序列是什么,代价都必须是相同的,就像任何平摊分析方法一样。 回顾上一节中修改后的堆栈,每个操作的成本是 1 2 3 Push: 1 Pop: 1 Multipop: min(栈。大小、k) Multipop的成本将是<年代pan class="katex"> k k k如果<年代pan class="katex"> k k k小于堆栈中元素的数量,或者等于堆栈的大小。把平摊代价赋给这些函数,我们得到 1 2 3 Push: 2 Pop: 0 Multipop: 0 这里值得注意的是,multipop的平摊成本是恒定的,而它的实际成本是可变的。 最后一步是要证明它是可以支付的任何使用平摊代价的操作序列。这一步用金钱是很有帮助的,所以1美元等于1成本。 如果我们把这个堆栈看成是一个实际的板的堆栈,这就更清楚了。把一个盘子推到栈上就是把这个盘子放到栈顶的动作。弹它是指把顶板拿下来的动作。因此,在本例中,当一个盘子被推入堆栈时,我们为操作的实际成本支付1美元,并留下1美元的信用。这是因为我们用push的平摊代价(2美元)减去实际代价(1美元),就剩下1美元。我们把那美元放在刚刚推过的盘子上。所以,在任意时刻,每个盘子都有1美元的信用额度。 盘子上的1美元将作为弹出盘子所需的钱。取出盘子需要1美元因为取出盘子的平摊代价(0美元)减去取出盘子的实际代价(1美元)等于- 1美元。在任何时候,每个盘子上面都正好有1美元,可以用来把盘子从盘子堆中取出来。 Multipop使用pop作为子程序。在堆栈上调用multipop不需要花钱,但是multipop中的pop子例程将使用每个盘子上的$1来删除它。 因为总是有1美元在每个盘子的上面,信用永远不会是负的。从本质上讲,这和我们之前探讨的想法是一样的<一个t一个rget="_blank" rel="nofollow" href="#aggregate-analysis">聚合分析.在某些内容被压入堆栈之前,执行pop或multipop没有任何意义。没有什么可以爆炸的!所以,最坏情况下的成本<年代pan class="katex"> n n n操作<年代pan class="katex"> O ( n ) O (n) O(n).
一项业务的摊销成本是在业务的实际成本和存入或用完的信贷之间进行分配。每个操作可以有不同的平摊成本,不像<一个t一个rget="_blank" rel="nofollow" href="#aggregate-analysis">聚合分析.为每个操作选择平摊代价是很重要的,但是对于一个给定的操作,无论操作序列是什么,代价都必须是相同的,就像任何平摊分析方法一样。 回顾上一节中修改后的堆栈,每个操作的成本是 1 2 3 Push: 1 Pop: 1 Multipop: min(栈。大小、k) Multipop的成本将是<年代pan class="katex"> k k k如果<年代pan class="katex"> k k k小于堆栈中元素的数量,或者等于堆栈的大小。把平摊代价赋给这些函数,我们得到 1 2 3 Push: 2 Pop: 0 Multipop: 0 这里值得注意的是,multipop的平摊成本是恒定的,而它的实际成本是可变的。 最后一步是要证明它是可以支付的任何使用平摊代价的操作序列。这一步用金钱是很有帮助的,所以1美元等于1成本。 如果我们把这个堆栈看成是一个实际的板的堆栈,这就更清楚了。把一个盘子推到栈上就是把这个盘子放到栈顶的动作。弹它是指把顶板拿下来的动作。因此,在本例中,当一个盘子被推入堆栈时,我们为操作的实际成本支付1美元,并留下1美元的信用。这是因为我们用push的平摊代价(2美元)减去实际代价(1美元),就剩下1美元。我们把那美元放在刚刚推过的盘子上。所以,在任意时刻,每个盘子都有1美元的信用额度。 盘子上的1美元将作为弹出盘子所需的钱。取出盘子需要1美元因为取出盘子的平摊代价(0美元)减去取出盘子的实际代价(1美元)等于- 1美元。在任何时候,每个盘子上面都正好有1美元,可以用来把盘子从盘子堆中取出来。 Multipop使用pop作为子程序。在堆栈上调用multipop不需要花钱,但是multipop中的pop子例程将使用每个盘子上的$1来删除它。 因为总是有1美元在每个盘子的上面,信用永远不会是负的。从本质上讲,这和我们之前探讨的想法是一样的<一个t一个rget="_blank" rel="nofollow" href="#aggregate-analysis">聚合分析.在某些内容被压入堆栈之前,执行pop或multipop没有任何意义。没有什么可以爆炸的!所以,最坏情况下的成本<年代pan class="katex"> n n n操作<年代pan class="katex"> O ( n ) O (n) O(n).
回顾上一节中修改后的堆栈,每个操作的成本是 1 2 3 Push: 1 Pop: 1 Multipop: min(栈。大小、k) Multipop的成本将是<年代pan class="katex"> k k k如果<年代pan class="katex"> k k k小于堆栈中元素的数量,或者等于堆栈的大小。把平摊代价赋给这些函数,我们得到 1 2 3 Push: 2 Pop: 0 Multipop: 0 这里值得注意的是,multipop的平摊成本是恒定的,而它的实际成本是可变的。 最后一步是要证明它是可以支付的任何使用平摊代价的操作序列。这一步用金钱是很有帮助的,所以1美元等于1成本。 如果我们把这个堆栈看成是一个实际的板的堆栈,这就更清楚了。把一个盘子推到栈上就是把这个盘子放到栈顶的动作。弹它是指把顶板拿下来的动作。因此,在本例中,当一个盘子被推入堆栈时,我们为操作的实际成本支付1美元,并留下1美元的信用。这是因为我们用push的平摊代价(2美元)减去实际代价(1美元),就剩下1美元。我们把那美元放在刚刚推过的盘子上。所以,在任意时刻,每个盘子都有1美元的信用额度。 盘子上的1美元将作为弹出盘子所需的钱。取出盘子需要1美元因为取出盘子的平摊代价(0美元)减去取出盘子的实际代价(1美元)等于- 1美元。在任何时候,每个盘子上面都正好有1美元,可以用来把盘子从盘子堆中取出来。 Multipop使用pop作为子程序。在堆栈上调用multipop不需要花钱,但是multipop中的pop子例程将使用每个盘子上的$1来删除它。 因为总是有1美元在每个盘子的上面,信用永远不会是负的。从本质上讲,这和我们之前探讨的想法是一样的<一个t一个rget="_blank" rel="nofollow" href="#aggregate-analysis">聚合分析.在某些内容被压入堆栈之前,执行pop或multipop没有任何意义。没有什么可以爆炸的!所以,最坏情况下的成本<年代pan class="katex"> n n n操作<年代pan class="katex"> O ( n ) O (n) O(n).
1 2 3
Push: 1 Pop: 1 Multipop: min(栈。大小、k)
Multipop的成本将是<年代pan class="katex"> k k k如果<年代pan class="katex"> k k k小于堆栈中元素的数量,或者等于堆栈的大小。把平摊代价赋给这些函数,我们得到 1 2 3 Push: 2 Pop: 0 Multipop: 0 这里值得注意的是,multipop的平摊成本是恒定的,而它的实际成本是可变的。 最后一步是要证明它是可以支付的任何使用平摊代价的操作序列。这一步用金钱是很有帮助的,所以1美元等于1成本。 如果我们把这个堆栈看成是一个实际的板的堆栈,这就更清楚了。把一个盘子推到栈上就是把这个盘子放到栈顶的动作。弹它是指把顶板拿下来的动作。因此,在本例中,当一个盘子被推入堆栈时,我们为操作的实际成本支付1美元,并留下1美元的信用。这是因为我们用push的平摊代价(2美元)减去实际代价(1美元),就剩下1美元。我们把那美元放在刚刚推过的盘子上。所以,在任意时刻,每个盘子都有1美元的信用额度。 盘子上的1美元将作为弹出盘子所需的钱。取出盘子需要1美元因为取出盘子的平摊代价(0美元)减去取出盘子的实际代价(1美元)等于- 1美元。在任何时候,每个盘子上面都正好有1美元,可以用来把盘子从盘子堆中取出来。 Multipop使用pop作为子程序。在堆栈上调用multipop不需要花钱,但是multipop中的pop子例程将使用每个盘子上的$1来删除它。 因为总是有1美元在每个盘子的上面,信用永远不会是负的。从本质上讲,这和我们之前探讨的想法是一样的<一个t一个rget="_blank" rel="nofollow" href="#aggregate-analysis">聚合分析.在某些内容被压入堆栈之前,执行pop或multipop没有任何意义。没有什么可以爆炸的!所以,最坏情况下的成本<年代pan class="katex"> n n n操作<年代pan class="katex"> O ( n ) O (n) O(n).
Push: 2 Pop: 0 Multipop: 0
这里值得注意的是,multipop的平摊成本是恒定的,而它的实际成本是可变的。 最后一步是要证明它是可以支付的任何使用平摊代价的操作序列。这一步用金钱是很有帮助的,所以1美元等于1成本。 如果我们把这个堆栈看成是一个实际的板的堆栈,这就更清楚了。把一个盘子推到栈上就是把这个盘子放到栈顶的动作。弹它是指把顶板拿下来的动作。因此,在本例中,当一个盘子被推入堆栈时,我们为操作的实际成本支付1美元,并留下1美元的信用。这是因为我们用push的平摊代价(2美元)减去实际代价(1美元),就剩下1美元。我们把那美元放在刚刚推过的盘子上。所以,在任意时刻,每个盘子都有1美元的信用额度。 盘子上的1美元将作为弹出盘子所需的钱。取出盘子需要1美元因为取出盘子的平摊代价(0美元)减去取出盘子的实际代价(1美元)等于- 1美元。在任何时候,每个盘子上面都正好有1美元,可以用来把盘子从盘子堆中取出来。 Multipop使用pop作为子程序。在堆栈上调用multipop不需要花钱,但是multipop中的pop子例程将使用每个盘子上的$1来删除它。 因为总是有1美元在每个盘子的上面,信用永远不会是负的。从本质上讲,这和我们之前探讨的想法是一样的<一个t一个rget="_blank" rel="nofollow" href="#aggregate-analysis">聚合分析.在某些内容被压入堆栈之前,执行pop或multipop没有任何意义。没有什么可以爆炸的!所以,最坏情况下的成本<年代pan class="katex"> n n n操作<年代pan class="katex"> O ( n ) O (n) O(n).
最后一步是要证明它是可以支付的任何使用平摊代价的操作序列。这一步用金钱是很有帮助的,所以1美元等于1成本。 如果我们把这个堆栈看成是一个实际的板的堆栈,这就更清楚了。把一个盘子推到栈上就是把这个盘子放到栈顶的动作。弹它是指把顶板拿下来的动作。因此,在本例中,当一个盘子被推入堆栈时,我们为操作的实际成本支付1美元,并留下1美元的信用。这是因为我们用push的平摊代价(2美元)减去实际代价(1美元),就剩下1美元。我们把那美元放在刚刚推过的盘子上。所以,在任意时刻,每个盘子都有1美元的信用额度。 盘子上的1美元将作为弹出盘子所需的钱。取出盘子需要1美元因为取出盘子的平摊代价(0美元)减去取出盘子的实际代价(1美元)等于- 1美元。在任何时候,每个盘子上面都正好有1美元,可以用来把盘子从盘子堆中取出来。 Multipop使用pop作为子程序。在堆栈上调用multipop不需要花钱,但是multipop中的pop子例程将使用每个盘子上的$1来删除它。 因为总是有1美元在每个盘子的上面,信用永远不会是负的。从本质上讲,这和我们之前探讨的想法是一样的<一个t一个rget="_blank" rel="nofollow" href="#aggregate-analysis">聚合分析.在某些内容被压入堆栈之前,执行pop或multipop没有任何意义。没有什么可以爆炸的!所以,最坏情况下的成本<年代pan class="katex"> n n n操作<年代pan class="katex"> O ( n ) O (n) O(n).
如果我们把这个堆栈看成是一个实际的板的堆栈,这就更清楚了。把一个盘子推到栈上就是把这个盘子放到栈顶的动作。弹它是指把顶板拿下来的动作。因此,在本例中,当一个盘子被推入堆栈时,我们为操作的实际成本支付1美元,并留下1美元的信用。这是因为我们用push的平摊代价(2美元)减去实际代价(1美元),就剩下1美元。我们把那美元放在刚刚推过的盘子上。所以,在任意时刻,每个盘子都有1美元的信用额度。 盘子上的1美元将作为弹出盘子所需的钱。取出盘子需要1美元因为取出盘子的平摊代价(0美元)减去取出盘子的实际代价(1美元)等于- 1美元。在任何时候,每个盘子上面都正好有1美元,可以用来把盘子从盘子堆中取出来。 Multipop使用pop作为子程序。在堆栈上调用multipop不需要花钱,但是multipop中的pop子例程将使用每个盘子上的$1来删除它。 因为总是有1美元在每个盘子的上面,信用永远不会是负的。从本质上讲,这和我们之前探讨的想法是一样的<一个t一个rget="_blank" rel="nofollow" href="#aggregate-analysis">聚合分析.在某些内容被压入堆栈之前,执行pop或multipop没有任何意义。没有什么可以爆炸的!所以,最坏情况下的成本<年代pan class="katex"> n n n操作<年代pan class="katex"> O ( n ) O (n) O(n).
盘子上的1美元将作为弹出盘子所需的钱。取出盘子需要1美元因为取出盘子的平摊代价(0美元)减去取出盘子的实际代价(1美元)等于- 1美元。在任何时候,每个盘子上面都正好有1美元,可以用来把盘子从盘子堆中取出来。 Multipop使用pop作为子程序。在堆栈上调用multipop不需要花钱,但是multipop中的pop子例程将使用每个盘子上的$1来删除它。 因为总是有1美元在每个盘子的上面,信用永远不会是负的。从本质上讲,这和我们之前探讨的想法是一样的<一个t一个rget="_blank" rel="nofollow" href="#aggregate-analysis">聚合分析.在某些内容被压入堆栈之前,执行pop或multipop没有任何意义。没有什么可以爆炸的!所以,最坏情况下的成本<年代pan class="katex"> n n n操作<年代pan class="katex"> O ( n ) O (n) O(n).
Multipop使用pop作为子程序。在堆栈上调用multipop不需要花钱,但是multipop中的pop子例程将使用每个盘子上的$1来删除它。 因为总是有1美元在每个盘子的上面,信用永远不会是负的。从本质上讲,这和我们之前探讨的想法是一样的<一个t一个rget="_blank" rel="nofollow" href="#aggregate-analysis">聚合分析.在某些内容被压入堆栈之前,执行pop或multipop没有任何意义。没有什么可以爆炸的!所以,最坏情况下的成本<年代pan class="katex"> n n n操作<年代pan class="katex"> O ( n ) O (n) O(n).
因为总是有1美元在每个盘子的上面,信用永远不会是负的。从本质上讲,这和我们之前探讨的想法是一样的<一个t一个rget="_blank" rel="nofollow" href="#aggregate-analysis">聚合分析.在某些内容被压入堆栈之前,执行pop或multipop没有任何意义。没有什么可以爆炸的!所以,最坏情况下的成本<年代pan class="katex"> n n n操作<年代pan class="katex"> O ( n ) O (n) O(n).
潜在方法类似于会计方法。然而,这种潜在方法并不考虑成本和信用方面的分析,而是认为已经完成的工作是<年代trong>势能这可以为以后的手术买单。这类似于把一块石头滚上山,产生势能,然后不费力气地把它拉下山。然而,与计算方法不同的是,势能是与数据结构作为一个整体相关联的,而不是与单个操作相关联的。 潜在方法的工作原理如下:它从一个初始数据结构开始,<年代pan class="katex"> D 0 数 D0.然后<年代pan class="katex"> n n n执行操作,将初始数据结构转换为<年代pan class="katex"> D 1 , D 2 , D 3. , . . . , D n D_1, d_2, d_3,…, D_n D1,D2,D3.,...,Dn.<年代pan class="katex"> c 我 为c_i c我费用将与<年代pan class="katex"> 我 th 我^ \文本{th} 我th操作,<年代pan class="katex"> D 我 d1 D我数据结构是由<年代pan class="katex"> 我 th 我^ \文本{th} 我th操作。 Φ \φ Φ是<年代trong>势函数哪个映射数据结构<年代pan class="katex"> D D D许多<年代pan class="katex"> Φ ( D ) \φ(D) Φ(D),与该数据结构相关的潜力。的<年代trong>摊余成本的<年代pan class="katex"> 我 我 我运算定义为 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) . a_i = c_i + (D_i) - (D_{i-1}) 一个我=c我+Φ(D我)−Φ(D我−1). 这就意味着结束了<年代pan class="katex"> n n n总平摊成本是 ∑ 我 = 1 n 一个 我 = ∑ 我 = 1 n ( c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) ) . \ sum_ {i = 1} ^ = {n} a_i \ sum_ {i = 1} ^ {n} \大(为c_i + \φ(d1) - \φ(D_张{})\大)。 我=1∑n一个我=我=1∑n(c我+Φ(D我)−Φ(D我−1)). 因为这是一个<一个href="//www.parkandroid.com/wiki/telescoping-series/" class="wiki_link" title="可伸缩的总和gydF4y2Ba" target="_blank">可伸缩的总和,它等于 ∑ 我 = 1 n c 我 + Φ ( D n ) − Φ ( D 0 ) . \sum_{i=1}^{n}c_i + \Phi(D_n) - Phi(D_0) 我=1∑nc我+Φ(Dn)−Φ(D0). 在这个方法中,它是要求那<年代pan class="katex"> Φ ( D 我 ) ≥ Φ ( D 0 ) \φ(d1) \组\φ(数) Φ(D我)≥Φ(D0)对所有<年代pan class="katex"> 我 我 我证明总的平摊成本<年代pan class="katex"> n n n操作是实际总成本的上限。一个典型的方法是定义<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0并显示<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0. 在操作序列的过程中<年代pan class="katex"> 我 th 我^ \文本{th} 我th操作会有一个电位差<年代pan class="katex"> Φ ( D 我 ) − Φ ( D 我 − 1 ) \φ(d1) - \φ(D_张{}) Φ(D我)−Φ(D我−1).如果这个值是正的,那么平摊代价<年代pan class="katex"> 一个 我 ai 一个我是对这个操作的过度收费,并且数据结构的势能会增加。如果为负,则为电荷不足,数据结构的势能将会减小。 让我们回顾一下修改后的堆栈。所选择的势函数就是堆栈上的项数。因此,在操作序列开始之前,<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0因为堆栈中没有项。对于以后的行动,很明显<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0因为堆栈中的项数不能为负数。 计算一个推操作的电位差,我们发现 Φ ( D 我 ) − Φ ( D 我 − 1 ) = ( 年代 t 一个 c k . 年代 我 z e + 1 ) − 年代 t 一个 c k . 年代 我 z e = 1. \Phi(D_i) - Phi(D_{i-1}) =大小+ 1)-堆栈。大小= 1。 Φ(D我)−Φ(D我−1)=(年代t一个ck.年代我ze+1)−年代t一个ck.年代我ze=1. 推操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 1 + 1 = 2. ai =为c_i + \φ(d1) - \φ(D_张{})= 1 + 1 = 2。 一个我=c我+Φ(D我)−Φ(D我−1)=1+1=2. 流行音乐和多流行音乐的电位差是多少?pop和multipop的平摊代价是多少? 显示答案 计算pop和multipop的平摊代价是相似的,所以这里只显示multipop。参数为的多输入操作的电位差<年代pan class="katex"> k k k是 Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k). 多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
潜在方法的工作原理如下:它从一个初始数据结构开始,<年代pan class="katex"> D 0 数 D0.然后<年代pan class="katex"> n n n执行操作,将初始数据结构转换为<年代pan class="katex"> D 1 , D 2 , D 3. , . . . , D n D_1, d_2, d_3,…, D_n D1,D2,D3.,...,Dn.<年代pan class="katex"> c 我 为c_i c我费用将与<年代pan class="katex"> 我 th 我^ \文本{th} 我th操作,<年代pan class="katex"> D 我 d1 D我数据结构是由<年代pan class="katex"> 我 th 我^ \文本{th} 我th操作。 Φ \φ Φ是<年代trong>势函数哪个映射数据结构<年代pan class="katex"> D D D许多<年代pan class="katex"> Φ ( D ) \φ(D) Φ(D),与该数据结构相关的潜力。的<年代trong>摊余成本的<年代pan class="katex"> 我 我 我运算定义为 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) . a_i = c_i + (D_i) - (D_{i-1}) 一个我=c我+Φ(D我)−Φ(D我−1). 这就意味着结束了<年代pan class="katex"> n n n总平摊成本是 ∑ 我 = 1 n 一个 我 = ∑ 我 = 1 n ( c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) ) . \ sum_ {i = 1} ^ = {n} a_i \ sum_ {i = 1} ^ {n} \大(为c_i + \φ(d1) - \φ(D_张{})\大)。 我=1∑n一个我=我=1∑n(c我+Φ(D我)−Φ(D我−1)). 因为这是一个<一个href="//www.parkandroid.com/wiki/telescoping-series/" class="wiki_link" title="可伸缩的总和gydF4y2Ba" target="_blank">可伸缩的总和,它等于 ∑ 我 = 1 n c 我 + Φ ( D n ) − Φ ( D 0 ) . \sum_{i=1}^{n}c_i + \Phi(D_n) - Phi(D_0) 我=1∑nc我+Φ(Dn)−Φ(D0). 在这个方法中,它是要求那<年代pan class="katex"> Φ ( D 我 ) ≥ Φ ( D 0 ) \φ(d1) \组\φ(数) Φ(D我)≥Φ(D0)对所有<年代pan class="katex"> 我 我 我证明总的平摊成本<年代pan class="katex"> n n n操作是实际总成本的上限。一个典型的方法是定义<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0并显示<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0. 在操作序列的过程中<年代pan class="katex"> 我 th 我^ \文本{th} 我th操作会有一个电位差<年代pan class="katex"> Φ ( D 我 ) − Φ ( D 我 − 1 ) \φ(d1) - \φ(D_张{}) Φ(D我)−Φ(D我−1).如果这个值是正的,那么平摊代价<年代pan class="katex"> 一个 我 ai 一个我是对这个操作的过度收费,并且数据结构的势能会增加。如果为负,则为电荷不足,数据结构的势能将会减小。 让我们回顾一下修改后的堆栈。所选择的势函数就是堆栈上的项数。因此,在操作序列开始之前,<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0因为堆栈中没有项。对于以后的行动,很明显<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0因为堆栈中的项数不能为负数。 计算一个推操作的电位差,我们发现 Φ ( D 我 ) − Φ ( D 我 − 1 ) = ( 年代 t 一个 c k . 年代 我 z e + 1 ) − 年代 t 一个 c k . 年代 我 z e = 1. \Phi(D_i) - Phi(D_{i-1}) =大小+ 1)-堆栈。大小= 1。 Φ(D我)−Φ(D我−1)=(年代t一个ck.年代我ze+1)−年代t一个ck.年代我ze=1. 推操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 1 + 1 = 2. ai =为c_i + \φ(d1) - \φ(D_张{})= 1 + 1 = 2。 一个我=c我+Φ(D我)−Φ(D我−1)=1+1=2. 流行音乐和多流行音乐的电位差是多少?pop和multipop的平摊代价是多少? 显示答案 计算pop和multipop的平摊代价是相似的,所以这里只显示multipop。参数为的多输入操作的电位差<年代pan class="katex"> k k k是 Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k). 多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
Φ \φ Φ是<年代trong>势函数哪个映射数据结构<年代pan class="katex"> D D D许多<年代pan class="katex"> Φ ( D ) \φ(D) Φ(D),与该数据结构相关的潜力。的<年代trong>摊余成本的<年代pan class="katex"> 我 我 我运算定义为 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) . a_i = c_i + (D_i) - (D_{i-1}) 一个我=c我+Φ(D我)−Φ(D我−1). 这就意味着结束了<年代pan class="katex"> n n n总平摊成本是 ∑ 我 = 1 n 一个 我 = ∑ 我 = 1 n ( c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) ) . \ sum_ {i = 1} ^ = {n} a_i \ sum_ {i = 1} ^ {n} \大(为c_i + \φ(d1) - \φ(D_张{})\大)。 我=1∑n一个我=我=1∑n(c我+Φ(D我)−Φ(D我−1)). 因为这是一个<一个href="//www.parkandroid.com/wiki/telescoping-series/" class="wiki_link" title="可伸缩的总和gydF4y2Ba" target="_blank">可伸缩的总和,它等于 ∑ 我 = 1 n c 我 + Φ ( D n ) − Φ ( D 0 ) . \sum_{i=1}^{n}c_i + \Phi(D_n) - Phi(D_0) 我=1∑nc我+Φ(Dn)−Φ(D0). 在这个方法中,它是要求那<年代pan class="katex"> Φ ( D 我 ) ≥ Φ ( D 0 ) \φ(d1) \组\φ(数) Φ(D我)≥Φ(D0)对所有<年代pan class="katex"> 我 我 我证明总的平摊成本<年代pan class="katex"> n n n操作是实际总成本的上限。一个典型的方法是定义<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0并显示<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0. 在操作序列的过程中<年代pan class="katex"> 我 th 我^ \文本{th} 我th操作会有一个电位差<年代pan class="katex"> Φ ( D 我 ) − Φ ( D 我 − 1 ) \φ(d1) - \φ(D_张{}) Φ(D我)−Φ(D我−1).如果这个值是正的,那么平摊代价<年代pan class="katex"> 一个 我 ai 一个我是对这个操作的过度收费,并且数据结构的势能会增加。如果为负,则为电荷不足,数据结构的势能将会减小。 让我们回顾一下修改后的堆栈。所选择的势函数就是堆栈上的项数。因此,在操作序列开始之前,<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0因为堆栈中没有项。对于以后的行动,很明显<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0因为堆栈中的项数不能为负数。 计算一个推操作的电位差,我们发现 Φ ( D 我 ) − Φ ( D 我 − 1 ) = ( 年代 t 一个 c k . 年代 我 z e + 1 ) − 年代 t 一个 c k . 年代 我 z e = 1. \Phi(D_i) - Phi(D_{i-1}) =大小+ 1)-堆栈。大小= 1。 Φ(D我)−Φ(D我−1)=(年代t一个ck.年代我ze+1)−年代t一个ck.年代我ze=1. 推操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 1 + 1 = 2. ai =为c_i + \φ(d1) - \φ(D_张{})= 1 + 1 = 2。 一个我=c我+Φ(D我)−Φ(D我−1)=1+1=2. 流行音乐和多流行音乐的电位差是多少?pop和multipop的平摊代价是多少? 显示答案 计算pop和multipop的平摊代价是相似的,所以这里只显示multipop。参数为的多输入操作的电位差<年代pan class="katex"> k k k是 Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k). 多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) . a_i = c_i + (D_i) - (D_{i-1}) 一个我=c我+Φ(D我)−Φ(D我−1).
这就意味着结束了<年代pan class="katex"> n n n总平摊成本是 ∑ 我 = 1 n 一个 我 = ∑ 我 = 1 n ( c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) ) . \ sum_ {i = 1} ^ = {n} a_i \ sum_ {i = 1} ^ {n} \大(为c_i + \φ(d1) - \φ(D_张{})\大)。 我=1∑n一个我=我=1∑n(c我+Φ(D我)−Φ(D我−1)). 因为这是一个<一个href="//www.parkandroid.com/wiki/telescoping-series/" class="wiki_link" title="可伸缩的总和gydF4y2Ba" target="_blank">可伸缩的总和,它等于 ∑ 我 = 1 n c 我 + Φ ( D n ) − Φ ( D 0 ) . \sum_{i=1}^{n}c_i + \Phi(D_n) - Phi(D_0) 我=1∑nc我+Φ(Dn)−Φ(D0). 在这个方法中,它是要求那<年代pan class="katex"> Φ ( D 我 ) ≥ Φ ( D 0 ) \φ(d1) \组\φ(数) Φ(D我)≥Φ(D0)对所有<年代pan class="katex"> 我 我 我证明总的平摊成本<年代pan class="katex"> n n n操作是实际总成本的上限。一个典型的方法是定义<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0并显示<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0. 在操作序列的过程中<年代pan class="katex"> 我 th 我^ \文本{th} 我th操作会有一个电位差<年代pan class="katex"> Φ ( D 我 ) − Φ ( D 我 − 1 ) \φ(d1) - \φ(D_张{}) Φ(D我)−Φ(D我−1).如果这个值是正的,那么平摊代价<年代pan class="katex"> 一个 我 ai 一个我是对这个操作的过度收费,并且数据结构的势能会增加。如果为负,则为电荷不足,数据结构的势能将会减小。 让我们回顾一下修改后的堆栈。所选择的势函数就是堆栈上的项数。因此,在操作序列开始之前,<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0因为堆栈中没有项。对于以后的行动,很明显<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0因为堆栈中的项数不能为负数。 计算一个推操作的电位差,我们发现 Φ ( D 我 ) − Φ ( D 我 − 1 ) = ( 年代 t 一个 c k . 年代 我 z e + 1 ) − 年代 t 一个 c k . 年代 我 z e = 1. \Phi(D_i) - Phi(D_{i-1}) =大小+ 1)-堆栈。大小= 1。 Φ(D我)−Φ(D我−1)=(年代t一个ck.年代我ze+1)−年代t一个ck.年代我ze=1. 推操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 1 + 1 = 2. ai =为c_i + \φ(d1) - \φ(D_张{})= 1 + 1 = 2。 一个我=c我+Φ(D我)−Φ(D我−1)=1+1=2. 流行音乐和多流行音乐的电位差是多少?pop和multipop的平摊代价是多少? 显示答案 计算pop和multipop的平摊代价是相似的,所以这里只显示multipop。参数为的多输入操作的电位差<年代pan class="katex"> k k k是 Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k). 多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
∑ 我 = 1 n 一个 我 = ∑ 我 = 1 n ( c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) ) . \ sum_ {i = 1} ^ = {n} a_i \ sum_ {i = 1} ^ {n} \大(为c_i + \φ(d1) - \φ(D_张{})\大)。 我=1∑n一个我=我=1∑n(c我+Φ(D我)−Φ(D我−1)).
因为这是一个<一个href="//www.parkandroid.com/wiki/telescoping-series/" class="wiki_link" title="可伸缩的总和gydF4y2Ba" target="_blank">可伸缩的总和,它等于 ∑ 我 = 1 n c 我 + Φ ( D n ) − Φ ( D 0 ) . \sum_{i=1}^{n}c_i + \Phi(D_n) - Phi(D_0) 我=1∑nc我+Φ(Dn)−Φ(D0). 在这个方法中,它是要求那<年代pan class="katex"> Φ ( D 我 ) ≥ Φ ( D 0 ) \φ(d1) \组\φ(数) Φ(D我)≥Φ(D0)对所有<年代pan class="katex"> 我 我 我证明总的平摊成本<年代pan class="katex"> n n n操作是实际总成本的上限。一个典型的方法是定义<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0并显示<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0. 在操作序列的过程中<年代pan class="katex"> 我 th 我^ \文本{th} 我th操作会有一个电位差<年代pan class="katex"> Φ ( D 我 ) − Φ ( D 我 − 1 ) \φ(d1) - \φ(D_张{}) Φ(D我)−Φ(D我−1).如果这个值是正的,那么平摊代价<年代pan class="katex"> 一个 我 ai 一个我是对这个操作的过度收费,并且数据结构的势能会增加。如果为负,则为电荷不足,数据结构的势能将会减小。 让我们回顾一下修改后的堆栈。所选择的势函数就是堆栈上的项数。因此,在操作序列开始之前,<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0因为堆栈中没有项。对于以后的行动,很明显<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0因为堆栈中的项数不能为负数。 计算一个推操作的电位差,我们发现 Φ ( D 我 ) − Φ ( D 我 − 1 ) = ( 年代 t 一个 c k . 年代 我 z e + 1 ) − 年代 t 一个 c k . 年代 我 z e = 1. \Phi(D_i) - Phi(D_{i-1}) =大小+ 1)-堆栈。大小= 1。 Φ(D我)−Φ(D我−1)=(年代t一个ck.年代我ze+1)−年代t一个ck.年代我ze=1. 推操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 1 + 1 = 2. ai =为c_i + \φ(d1) - \φ(D_张{})= 1 + 1 = 2。 一个我=c我+Φ(D我)−Φ(D我−1)=1+1=2. 流行音乐和多流行音乐的电位差是多少?pop和multipop的平摊代价是多少? 显示答案 计算pop和multipop的平摊代价是相似的,所以这里只显示multipop。参数为的多输入操作的电位差<年代pan class="katex"> k k k是 Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k). 多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
∑ 我 = 1 n c 我 + Φ ( D n ) − Φ ( D 0 ) . \sum_{i=1}^{n}c_i + \Phi(D_n) - Phi(D_0) 我=1∑nc我+Φ(Dn)−Φ(D0).
在这个方法中,它是要求那<年代pan class="katex"> Φ ( D 我 ) ≥ Φ ( D 0 ) \φ(d1) \组\φ(数) Φ(D我)≥Φ(D0)对所有<年代pan class="katex"> 我 我 我证明总的平摊成本<年代pan class="katex"> n n n操作是实际总成本的上限。一个典型的方法是定义<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0并显示<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0. 在操作序列的过程中<年代pan class="katex"> 我 th 我^ \文本{th} 我th操作会有一个电位差<年代pan class="katex"> Φ ( D 我 ) − Φ ( D 我 − 1 ) \φ(d1) - \φ(D_张{}) Φ(D我)−Φ(D我−1).如果这个值是正的,那么平摊代价<年代pan class="katex"> 一个 我 ai 一个我是对这个操作的过度收费,并且数据结构的势能会增加。如果为负,则为电荷不足,数据结构的势能将会减小。 让我们回顾一下修改后的堆栈。所选择的势函数就是堆栈上的项数。因此,在操作序列开始之前,<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0因为堆栈中没有项。对于以后的行动,很明显<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0因为堆栈中的项数不能为负数。 计算一个推操作的电位差,我们发现 Φ ( D 我 ) − Φ ( D 我 − 1 ) = ( 年代 t 一个 c k . 年代 我 z e + 1 ) − 年代 t 一个 c k . 年代 我 z e = 1. \Phi(D_i) - Phi(D_{i-1}) =大小+ 1)-堆栈。大小= 1。 Φ(D我)−Φ(D我−1)=(年代t一个ck.年代我ze+1)−年代t一个ck.年代我ze=1. 推操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 1 + 1 = 2. ai =为c_i + \φ(d1) - \φ(D_张{})= 1 + 1 = 2。 一个我=c我+Φ(D我)−Φ(D我−1)=1+1=2. 流行音乐和多流行音乐的电位差是多少?pop和multipop的平摊代价是多少? 显示答案 计算pop和multipop的平摊代价是相似的,所以这里只显示multipop。参数为的多输入操作的电位差<年代pan class="katex"> k k k是 Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k). 多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
在操作序列的过程中<年代pan class="katex"> 我 th 我^ \文本{th} 我th操作会有一个电位差<年代pan class="katex"> Φ ( D 我 ) − Φ ( D 我 − 1 ) \φ(d1) - \φ(D_张{}) Φ(D我)−Φ(D我−1).如果这个值是正的,那么平摊代价<年代pan class="katex"> 一个 我 ai 一个我是对这个操作的过度收费,并且数据结构的势能会增加。如果为负,则为电荷不足,数据结构的势能将会减小。 让我们回顾一下修改后的堆栈。所选择的势函数就是堆栈上的项数。因此,在操作序列开始之前,<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0因为堆栈中没有项。对于以后的行动,很明显<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0因为堆栈中的项数不能为负数。 计算一个推操作的电位差,我们发现 Φ ( D 我 ) − Φ ( D 我 − 1 ) = ( 年代 t 一个 c k . 年代 我 z e + 1 ) − 年代 t 一个 c k . 年代 我 z e = 1. \Phi(D_i) - Phi(D_{i-1}) =大小+ 1)-堆栈。大小= 1。 Φ(D我)−Φ(D我−1)=(年代t一个ck.年代我ze+1)−年代t一个ck.年代我ze=1. 推操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 1 + 1 = 2. ai =为c_i + \φ(d1) - \φ(D_张{})= 1 + 1 = 2。 一个我=c我+Φ(D我)−Φ(D我−1)=1+1=2. 流行音乐和多流行音乐的电位差是多少?pop和multipop的平摊代价是多少? 显示答案 计算pop和multipop的平摊代价是相似的,所以这里只显示multipop。参数为的多输入操作的电位差<年代pan class="katex"> k k k是 Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k). 多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
让我们回顾一下修改后的堆栈。所选择的势函数就是堆栈上的项数。因此,在操作序列开始之前,<年代pan class="katex"> Φ ( D 0 ) = 0 \φ(数)= 0 Φ(D0)=0因为堆栈中没有项。对于以后的行动,很明显<年代pan class="katex"> Φ ( D 我 ) ≥ 0 \φ(d1) \组0 Φ(D我)≥0因为堆栈中的项数不能为负数。 计算一个推操作的电位差,我们发现 Φ ( D 我 ) − Φ ( D 我 − 1 ) = ( 年代 t 一个 c k . 年代 我 z e + 1 ) − 年代 t 一个 c k . 年代 我 z e = 1. \Phi(D_i) - Phi(D_{i-1}) =大小+ 1)-堆栈。大小= 1。 Φ(D我)−Φ(D我−1)=(年代t一个ck.年代我ze+1)−年代t一个ck.年代我ze=1. 推操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 1 + 1 = 2. ai =为c_i + \φ(d1) - \φ(D_张{})= 1 + 1 = 2。 一个我=c我+Φ(D我)−Φ(D我−1)=1+1=2. 流行音乐和多流行音乐的电位差是多少?pop和multipop的平摊代价是多少? 显示答案 计算pop和multipop的平摊代价是相似的,所以这里只显示multipop。参数为的多输入操作的电位差<年代pan class="katex"> k k k是 Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k). 多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
计算一个推操作的电位差,我们发现 Φ ( D 我 ) − Φ ( D 我 − 1 ) = ( 年代 t 一个 c k . 年代 我 z e + 1 ) − 年代 t 一个 c k . 年代 我 z e = 1. \Phi(D_i) - Phi(D_{i-1}) =大小+ 1)-堆栈。大小= 1。 Φ(D我)−Φ(D我−1)=(年代t一个ck.年代我ze+1)−年代t一个ck.年代我ze=1. 推操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 1 + 1 = 2. ai =为c_i + \φ(d1) - \φ(D_张{})= 1 + 1 = 2。 一个我=c我+Φ(D我)−Φ(D我−1)=1+1=2. 流行音乐和多流行音乐的电位差是多少?pop和multipop的平摊代价是多少? 显示答案 计算pop和multipop的平摊代价是相似的,所以这里只显示multipop。参数为的多输入操作的电位差<年代pan class="katex"> k k k是 Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k). 多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
Φ ( D 我 ) − Φ ( D 我 − 1 ) = ( 年代 t 一个 c k . 年代 我 z e + 1 ) − 年代 t 一个 c k . 年代 我 z e = 1. \Phi(D_i) - Phi(D_{i-1}) =大小+ 1)-堆栈。大小= 1。 Φ(D我)−Φ(D我−1)=(年代t一个ck.年代我ze+1)−年代t一个ck.年代我ze=1.
推操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 1 + 1 = 2. ai =为c_i + \φ(d1) - \φ(D_张{})= 1 + 1 = 2。 一个我=c我+Φ(D我)−Φ(D我−1)=1+1=2. 流行音乐和多流行音乐的电位差是多少?pop和multipop的平摊代价是多少? 显示答案 计算pop和multipop的平摊代价是相似的,所以这里只显示multipop。参数为的多输入操作的电位差<年代pan class="katex"> k k k是 Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k). 多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 1 + 1 = 2. ai =为c_i + \φ(d1) - \φ(D_张{})= 1 + 1 = 2。 一个我=c我+Φ(D我)−Φ(D我−1)=1+1=2.
流行音乐和多流行音乐的电位差是多少?pop和multipop的平摊代价是多少? 显示答案 计算pop和multipop的平摊代价是相似的,所以这里只显示multipop。参数为的多输入操作的电位差<年代pan class="katex"> k k k是 Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k). 多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
计算pop和multipop的平摊代价是相似的,所以这里只显示multipop。参数为的多输入操作的电位差<年代pan class="katex"> k k k是 Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k). 多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
Φ ( D 我 ) − Φ ( D 我 − 1 ) = − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) . \Phi(D_i) - Phi(D_{i-1}) = - Phi(D_{i-1})大小,k)。 Φ(D我)−Φ(D我−1)=−最小值(年代t一个ck.年代我ze,k).
多重操作的平摊代价是 一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =
一个 我 = c 我 + Φ ( D 我 ) − Φ ( D 我 − 1 ) = 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) + ( − 最小值 ( 年代 t 一个 c k . 年代 我 z e , k ) ) =