0

最近去面试，面试官问了我这个问题。

有 k+1 堆大小1, 2^1, 2^2, 2^3, ...,2^k。让我们stack 1, stack 2, ... stack k+1分别称呼它们。当insert(x)被调用时，元素被插入第一个堆栈，即大小为 1 的堆栈。如果该堆栈已满，则该堆栈的元素被移动到下一个堆栈，然后元素被插入第一个堆栈。它类似于管道操作。堆栈 1 将元素推入堆栈 2，堆栈 2 推入堆栈 3，依此类推。如果所有堆栈都已满，那么我们会抛出一个错误，说明堆栈溢出。还有另一个操作，delete(x)。它从堆栈堆栈中删除 x。因此，如果 x 不是最顶部的元素，即它不存在于堆栈 1 中，则我们从中弹出元素，然后移动元素，然后再次尝试弹出，直到找到该元素并将其删除。插入和删除此实现的摊销复杂度是多少？

编辑 1：展示插入和删除的工作原理。
假设有 2 个堆栈，堆栈 1 和堆栈 2 的大小分别为 2^0 和 2^1。
迭代 0：堆栈 1 -> {}，堆栈 2 -> {}
迭代 1：插入（1）。堆栈 1 -> {1}，堆栈 2 -> {}，顶部 -> 1
迭代 2：插入（2）。堆栈 1 -> {2}，堆栈 2 -> {1}，顶部 -> 2
迭代 3：插入（3）。堆栈 1 -> {3}，堆栈 2 -> {2,1}，顶部 -> 3
迭代 4：插入（4）。溢出异常。堆栈 1 -> {3}，堆栈 2 -> {2,1}，顶部 -> 3
迭代 5：删除（2）。

  • 我们弹出 3，作为 2!=3 并继续。堆栈 1 -> {2}，堆栈 2 -> {1}，顶部 -> 2
  • 我们弹出 2 并返回。堆栈 1 -> {1}，堆栈 2 -> {}，顶部 -> 1
    迭代 6：插入（4）。Stack 1 -> {4}, Stack 2 -> {1}, top -> 3
    希望这两个操作现在都清楚了:)

我尽力而为，只能说出最坏情况的时间复杂度，即1+2^1+2^2+..+2^k（几何级数总和）。我不是在寻找最坏情况的时间复杂度。我什至无法达到摊销的复杂性。任何人都可以帮助理解如何计算这个问题的摊销复杂度吗？

4

1 回答 1

0

摊销分析最常用的工具是“潜在方法”，您可以查阅维基百科。

不过，我不擅长编程。让我们来谈谈宗教。让我们谈谈地狱。

地狱由k同心环组成，护城河将环隔开。从一层到下一层穿过护城河的唯一方法是雇佣摆渡人……但摆渡人会想要一枚金币作为回报。当然，在地狱中没有办法获得黄金；无论你被埋葬什么，这就是你可以花费的。（进入地狱的第一环也需要一枚硬币，顺便说一句。）

有趣的是，地狱戒指的规则与你的筹码规则相同。每个环比之前的大一倍（尽量不要考虑它的几何形状），每当一个环满了并且有人想搬进去时，首先那个环中的人必须雇用摆渡人来接他们到下一个环。

奇怪的是，地狱里只有一个摆渡人，他的船也只有一个人坐；他神奇地出现在他被雇用的任何护城河中，并花一分钟运送雇用他的人。所以一次只能运送一个人。

这意味着在整个地狱中，每分钟只花费一枚金币。这意味着如果一个新人想进入地狱，而前几个环都已满，摆渡人需要很多分钟才能将他带入地狱。

地狱现在是空的，但是在电影中说话的1023人刚刚死去，所以它即将被1023人填满。他们将用 1、2、4、8、16、32、64、128、256 和 512 人填充前 9 个圈子。

  1. 最终进入 512 环的每个人应该用多少枚硬币埋葬？每个最终将进入 256 环的人呢？
  2. 集体葬礼总共应该使用多少枚硬币？
  3. 摆渡人需要多长时间才能完成将所有人运送到位？
  4. 平均而言，每个人要等多久才能进入地狱？
  5. 的摊销复杂度是insert多少？
于 2015-02-10T16:26:03.420 回答