标签: amortized-analysis

它与渐近分析有什么不同？你什么时候使用它,为什么？

我读过一些似乎写得很好的文章,比如:

• http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

• http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

但我还是没有充分理解这些概念.

所以,有人可以为我简化吗？

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

正如TimeComplexity文档中所见,Python的list类型实现使用数组.

因此,如果正在使用数组并且我们做了一些追加,最终您将不得不重新分配空间并将所有信息复制到新空间.
毕竟,怎么可能是O(1)最坏的情况？

我们如何分析std :: vector中后面的插入(push_back)？它的摊销时间是每次插入O(1).特别是在史蒂芬牛逼Lavavej在Channel9的视频,并在此(17:42以后),他说,以获得最佳性能微软的这个方法的实现由大约1.5增加了向量的能力.

这个常数如何确定？

以下是维基百科上不相交集合林的联合/查找算法的细分:

• 准系统不相交的森林......(O(n))
  • ......按等级联盟......(现改进至O(log(n))
    • ...使用路径压缩(现在改进为O(a(n))有效O(1))

按等级实现联合需要每个节点保留一个rank字段用于比较目的.我的问题是,是否值得这个额外的空间？如果我按级别跳过联合而只是做路径压缩会发生什么？它够好吗？现在摊还的复杂性是多少？

发表评论意味着没有路径压缩的等级联合(摊销O(log(n)复杂性)足以满足大多数实际应用.这是对的.我要问的是另一种方式:如果你按级别跳过联合而只做路径压缩怎么办？

从某种意义上说,路径压缩是通过排名改进联合的额外步骤,这就是为什么可以省略额外步骤而不会带来灾难性后果的原因.但是联盟是否是路径压缩的必要中间步骤？我可以跳过它直接进行路径压缩,还是会发生灾难性的？

还有人指出,如果不按等级联合,重复的工会可以创建一个类似链表的结构.这意味着单一路径压缩操作可能O(n)在最坏的情况下采取.这当然会影响未来的运营,因此当我对许多运营进行摊销时,这种情况如何,这是我更感兴趣的.

我发现Haskell Data.Vector.*错过了C++ std::vector::push_back的功能.有grow/ unsafeGrow,但它们似乎有O(n)复杂性.

有没有办法在O(1)元素的摊销时间内增长向量？

我正在研究紧凑堆栈的想法——随着其大小的增加，其空间需求接近数组的空间需求。候选结构：

data Stack a
  = Empty
  | Zero (Stack a)
  | One !(SmallArray a) (Stack a)
  | Two !(SmallArray a) !(SmallArray a) (Stack a)
-- Invariant: the array size at depth `n` is `2^n`.

push :: a -> Stack a -> Stack a
push = pushA . pure

pushA :: SmallArray a -> Stack a -> Stack a
pushA sa Empty = One sa Empty
pushA sa (Zero more) = One sa more
pushA sa1 (One sa2 more) = Two …

这种结构对于实时应用是必需的 - 例如用户界面.(如果点击一个按钮需要0.1秒或0.2秒,用户不在乎,但是如果第100次点击强制执行一个非常懒的计算并且需要10秒才能继续,他们会关心.)

我正在阅读Okasaki的论文Purely functional data structures,他描述了一种有趣的通用方法,用于将具有分摊边界的惰性数据结构转换为具有每个操作的相同最坏情况边界的结构.这个想法是分配计算,以便在每次更新时强制部分未评估的thunk.

我想知道,是否有任何这样的实施标准集合(的Map,Set等等)在Haskell？

该容器包装说

每项操作的申报成本是最坏情况或摊销,但即使共享结构也仍然有效.

因此无法保证单个操作的最坏情况限制.有严格的变体Data.Map.Strict,但它们的键和值严格:

键和值参数被评估为WHNF; 在将值和值存储在地图中之前,它们将被评估为WHNF.

没有关于(可能)严格的结构.

在阅读splay树时,我发现了一些关于splay节点'X'的等级和维基百科中的摊销成本的表达式.它被赋予,{我们可以通过以下方式约束任何zig-zig或Zig-zag操作的摊销成本:

amortized cost = cost + P(tf) - P(ti) ? 3(rankf(x) - ranki(x)),

其中x是向根移动的节点,下标"f"和"i"分别表示在操作之后和之前.当对整个展开操作求和时,这个望远镜达到3(秩(根)),即O(log n).由于最多只有一个zig操作,这只会增加一个常量.}

我无法解释这一点.有人可以详细解释上面的内容.如果可能,举一些例子.

请提供一些链接,以解释其他定义树的定理

谢谢

std::map::erase(iterator)摊销的复杂性为O(1)(例如,见这里).虽然标准库没有规定实现,但事实上这意味着红黑树所需的重新平衡操作的数量是摊销的O(1).事实上,关于红黑树的维基百科条目似乎证实了这一点:

恢复红黑属性需要少量(O(log n)或摊销的O(1))颜色变化(实际上非​​常快)和不超过三次树旋转(两次插入).

但似乎没有链接(我在其他地方找不到它).

由于转数是恒定的,因此摊销取决于节点根路径上所需的重新着色次数.虽然平衡树中的大多数节点都朝向树的底部(因此平均路径是对数的),但它显然是摊销的O(1),这是令人惊讶和有趣的.如何证明摊销的固定成本？