算法| Set 5的分析(平摊分析介绍)- GeeksforGeeks188金宝搏滚球投注

算法| Set 5的分析(平摊分析导论)

难度等级:媒介
最后更新:2021年3月27日

平摊分析用于某些偶然操作非常慢，但大多数其他操作速度较快的算法。在平摊分析中，我们分析了一个操作序列，并保证其最坏情况平均时间小于某个特定昂贵操作的最坏情况平均时间。
使用平摊分析对其操作进行分析的示例数据结构是哈希表、不相交集和展开树。

让我们考虑一个简单哈希表插入的例子。我们如何决定表的大小?在空间和时间之间有一个取舍，如果我们使哈希表的大小变大，搜索时间会变慢，但所需的空间会变大。

动态表

这个折衷问题的解决方案是使用动态表(或数组)。其思想是在表满的时候增加表的大小。以下是表满时要遵循的步骤。
1)为一个更大的表分配内存，通常是旧表的两倍。
2)将旧表的内容复制到新表。
3)腾出旧桌子。

如果表有可用空间，只需在可用空间中插入新项。

使用上述方案，n次插入的时间复杂度是多少?
如果我们用简单的分析，插入的最坏情况代价是O(n)。因此，n次插入的最坏情况代价是n * O(n)也就是O(n²)。这个分析给出了一个上界，但不是n次插入的严格上界，因为所有的插入都不会花费Θ(n)时间。

AmortizedAnalysis

因此，利用平摊分析，我们可以证明动态表方案有O(1)的插入时间，这是一个很好的结果用于哈希。此外，动态表的概念被用于向量在c++中,ArrayList在Java中。

以下是一些重要的注意事项。
1)一系列操作的平摊成本可以看作是一个受薪人员的费用。一个人的月平均支出低于或等于工资，但他可以在一个特定的月花更多的钱买一辆车或其他东西。在其他月份，他或她会为昂贵的月份存钱。

2)上面为动态数组做的平摊分析的例子被调用聚合方法。有两种更有效的方法来做平摊分析会计方法和潜在的方法。我们将在单独的文章中讨论其他两种方法。

3)平摊分析不涉及概率。平均情况下的运行时间还有另一个不同的概念，算法使用随机化使它们更快，预期的运行时间比最坏情况的运行时间要快。这些算法采用随机分析方法进行分析。这些算法的例子是随机快速排序，快速选择和哈希。我们将很快在另一篇文章中介绍随机分析。

红黑树中插入的平摊分析

我们用势法讨论红黑树操作(插入)的平摊分析。

对于红黑树插入运算的平摊分析，我们使用了Potential(或物理学家的)方法。对于势法，我们定义一个势函数 $\φ$ 将数据结构映射为非负的实值。手术可以导致这种潜能的改变。

我们来定义势函数 $\φ$ 以以下方式:

(1) $\begin{equation*} g(n)=\begin{case} 0， & \text{if n是红色}。如果n是黑色的，没有红色的子结点}。0， & text{如果n是黑色的，有一个红色的子结点}。如果n是黑色的，并且有两个红色的子结点}。\ \ \{病例}结束\{方程*}结束$

其中n是红黑树的一个节点

势函数 $\φ$ = $\ sum_ {} g (n)$ ，在红黑树的所有节点上。

进一步，我们将操作的平摊时间定义为:

摊销的时间= c + $δφ\ \$ (h)

$δφ\ \$ (h) = $\φ$ (h) $\φ$ (h)
其中h和h '分别是红黑树在操作前和操作后的状态
C是操作的实际成本

潜力的变化对低成本作业应该是积极的，对高成本作业应该是消极的。

在红黑树的叶子上插入一个新节点。我们有以下任何一种红黑树的叶子:

插入及其平摊分析可以表示为:
(1)

这个插入是通过首先重新着色父元素和其他兄弟元素(红色)来执行的。然后该叶节点的祖父结点和叔父结点被考虑进一步重新着色，从而导致摊余成本是1(当叶节点的祖父结点为红色时)，2(当uncle of the leaf是黑色的，grandparent是黑色的)或者+ 1(当叔叔的叶子是红色的，爷爷的是黑色的)。插入可以显示为: