在第 5 课中的数据结构课程中给出的摊销分析的聚合方法中 O(n)/n=1 的情况如何 - 摊销分析：聚合方法？
问问题
197 次
1 回答
0
简短的回答
O(n)/n = cn/n = c = O(1)
长答案
我们使用摊销分析来分析一系列操作的成本，而不是单个操作的成本。在最后一种情况下，我们使用渐近分析（一些渐近符号是：Theta、Big O、Big Omega、Little O 和 Little Omega），但是当我们遇到一系列操作并想要了解该序列的成本。
原因是如果我们应用“常规”渐近分析，例如，我们在最坏情况分析中的渐近上限可能过于悲观。经典示例是插入动态数组。您将元素插入到动态分配的数组中，当它已满时，您定义新数组（例如两倍大）并复制所有元素。问题是大多数插入将在恒定时间内工作（或在 O(1) 中），但是当您需要重新定义数组时，它将花费线性时间 (O(n))，因为您需要复制所有元素.
所以想象一下，你插入 n 个元素，你只需要重新定义你的数组一次，然后你有 n 个操作，每个操作在最坏的情况下是 O(n)，因此在最坏的情况下操作序列的成本是 O( n^2)，考虑到您的大多数操作在最坏的情况下都是 O(1)，而其中只有一个是 O(n)，这似乎太悲观了。
我们将一系列操作的摊销成本定义为（n 个操作的成本）/n。在您的情况下，n 操作的成本是 O(n)，它等于 cn（其中 c 是某个常数），仅根据 Big O 表示法的定义，将其除以 n，您就得到 c，它等于 O (1) 因为，再一次，c 只是一些常数。
于 2017-05-09T08:02:09.937 回答