外行人的复杂程度如何？

Question

有人可以用非专业人的术语解释摊销的复杂性吗？我一直很难在网上找到一个精确的定义,我不知道它是如何与算法分析完全相关的.任何有用的东西,即使外部引用,都将受到高度赞赏.

Answer 1

摊销复杂性是每个操作的总费用,通过一系列操作进行评估.

这个想法是保证整个序列的总费用,同时允许单个操作比摊销成本贵得多.

示例:
C++的行为std::vector<>.当push_back()将矢量大小增加到其预分配值以上时,它会使分配的长度加倍.

因此单个执行push_back()可能需要一些O(N)时间(因为数组的内容被复制到新的内存分配).

但是,由于分配的大小加倍,下一次N-1调用push_back()将每次都需要O(1)时间来执行.因此,总的N操作仍需要O(N)时间; 从而给出每次操作push_back()的摊销成本O(1).

除非另有规定,否则摊销复杂性是任何操作序列的渐近最坏情况保证.这意味着:

• 正如非摊销的复杂性,用于摊销复杂的大O符号忽略这两个固定的初始开销和持续性能的因素.因此,为了评估大额摊销绩效,您通常可以假设任何一系列摊销操作都"足够长"以分摊固定的启动费用.具体来说,对于这个std::vector<>例子,这就是为什么你不必担心你是否真的会遇到N额外的操作:分析的渐近性质已经假定你会这样做.

• 除了任意长度,摊销分析不会对您正在测量成本的操作顺序做出假设 - 这是对任何可能的操作顺序的最坏情况保证.无论选择的操作多么糟糕(比如恶意对手!),摊销分析必须保证足够长的操作顺序可能不会比其摊销成本的总和更多.这就是为什么(除非特别提到作为限定词)"概率"和"平均情况"与摊销分析无关 - 不仅仅是普通的最坏情况大O分析!

Answer 2

在摊销分析中,执行一系列数据结构操作所需的时间对所有执行的操作进行平均...分期分析与平均情况分析的不同之处在于不涉及概率; 摊销分析保证了最坏情况下每项操作的平均表现.

(来自Cormen等人,"算法导论")

这可能有点令人困惑,因为它既说时间是平均的,也不是平均情况分析.因此,让我试着通过财务类比来解释这一点(实际上,"摊销"这个词最常与银行和会计相关联.)

假设您正在进行抽奖.(不是购买彩票,我们马上就可以买到,但是自己操作彩票.)你可以打印100,000张票,你将以1个货币单位出售.其中一张门票将使购买者拥有40,000个货币单位.

现在,假设你可以卖所有的门票,你站在挣6万个货币单位:100,000货币单位在销售,减去40000货币单位奖.对您而言,每张票的价值为0.60货币单位,按所有票价摊销.这是一个可靠的价值; 你可以存钱.如果您厌倦了自己出售门票,并且有人出现并提供以每个0.30货币单位出售它们,您就知道自己的确切位置.

对于彩票购买者来说,情况是不同的.购买者在购买彩票时预计会损失0.60个货币单位.但是,这是概率:购买者可能会购买每一天十张几个彩票30年(有点超过100000票),而没有获奖.或者他们可能会在一天内自发购买一张票,并赢得39,999个货币单位.

应用于数据结构分析,我们讨论的是第一种情况,我们在这种情况下分摊一些数据结构操作(比如插入)的成本.平均情况分析处理随机操作(例如,搜索)的预期值,其中我们无法计算所有操作的总成本,但我们可以提供对单个操作的预期成本的概率分析.

人们常说,摊销分析适用于高成本运作很少的情况,而且情况往往如此.但不总是.例如,考虑所谓的"银行家队列",它是一个先进先出(FIFO)队列,由两个堆栈组成.(这是一个经典的功能数据结构;你可以用不可变的单链节点构建廉价的LIFO堆栈,但廉价的FIFO并不是那么明显).这些操作实施如下:

put(x):  Push x on the right-hand stack.
y=get(): If the left-hand stack is empty:
           Pop each element off the right-hand stack and
             push it onto the left-hand stack. This effectively
             reverses the right-hand stack onto the left-hand stack.
         Pop and return the top element of the left-hand stack.

现在,我声称,put并且假设我以空队列开始和结束,并且get是的摊销成本O(1).分析很简单:我总是put在右手堆叠上,get从左手堆叠.所以除了这个If条款,每个put都是a push,每个get都是a pop,两者都是O(1).我不知道有多少次我会执行该If子句 - 它取决于puts和gets 的模式- 但我知道每个元素从右侧堆栈到左侧堆栈只移动一次.因此,整个n puts和n gets 序列的总成本是:n pushes,n pops和n moves,其中a move是a pop后跟a push:换句话说,2 n puts和gets导致2 n pushes和2 n pops.因此,单个put(或get)的摊销成本是一个push和一个pop.

请注意,银行家的队列被称为正是因为摊销的复杂性分析(以及"摊销"与财务的关联).银行家的队列是以前常见的面试问题的答案,虽然我认为它现在被认为是众所周知的:提出一个队列,在分摊的O(1)时间内实施以下三个操作:

1)获取并删除队列中最旧的元素,

2)将新元素放入队列中,

3)找到当前最大元素的值.

Answer 3

"摊销复杂性"的原则是,虽然当你这样做时某些东西可能相当复杂,但由于它并不常用,所以它被认为是"不复杂".例如,如果你创建一个需要不时平衡的二叉树 - 比如说每次2^n插入一次- 因为虽然平衡树非常复杂,但它只在每n次插入中发生一次(例如,一次插入数字256,然后再次在第512,第1024等).在所有其他插入中,复杂度为O(1) - 是的,每n次插入需要O(n)一次,但它只是1/n概率 - 因此我们将O(n)乘以1/n并得到O(1).所以这被称为"O(1)的摊销复杂性" - 因为当你添加更多元素时,重新平衡树所花费的时间是最小的.

Answer 4

摊销均值除以重复运行。保证最坏情况下的行为不会频繁发生。例如，如果最慢的情况是O（N），但是发生这种情况的机会仅为O（1 / N），否则该过程是O（1），则算法仍将具有摊销常数O（1）时间。只需考虑将每个O（N）运行的工作分解为N个其他运行。

该概念取决于是否有足够的运行来划分总时间。如果算法仅运行一次，或者每次运行都必须满足最后期限，那么最坏情况下的复杂性就更重要。

Answer 5

假设您正在尝试查找未排序数组中的第 k 个最小元素。对数组进行排序的时间复杂度为 O(n logn)。所以找到第k个最小的数就是定位索引，所以O(1)。

由于数组已经排序，因此我们不必再次排序。我们绝不会多次遇到最坏的情况。

如果我们执行 n 个查询来尝试找到第 k 个最小的，它仍然是 O(n logn)，因为它支配 O(1)。如果我们平均每个操作的时间，它将是：

(n logn)/n 或 O(logn)。所以，时间复杂度/操作数。

这是摊销的复杂性。

我觉得就是这样，我也是刚学的。。