3

我正在自学算法课程，我正在尝试解决以下问题：

描述一个存储一组实数的数据结构，它可以在 O(1) 的摊销时间内执行以下每个操作：

Insert(x) ：删除所有不大于 x 的元素，并将 x 添加到集合中。
FindMin() : 找到集合的最小值。

我意识到一旦你有了 Insert，findmin 就变得微不足道了，看看如何使用链表实现，你可以同时删除多个元素（即 O(1)），但找出要删除的链接（也就是 x 去哪里）似乎像 O(n) 或 O(log n) 操作，而不是 O(1)。问题给出了提示：考虑使用堆栈，但我看不出这有什么帮助。

任何帮助表示赞赏。

原始问题如下：

原始问题

4

2 回答 2

6

请注意，您的目标是获得 O(1)分摊时间，而不是 O(1) 时间。这意味着只要 n 次操作花费的时间不超过 O(n) 时间，您就可以在每次操作中做尽可能多的工作。

这是一个简单的解决方案。将元素按升序存储在堆栈中。要插入一个元素，请不断弹出堆栈，直到它为空或顶部元素大于 x，然后将 x 压入堆栈。要执行 find-min，请读取堆栈顶部。

Find-min 显然在 O(1) 时间内运行。现在让我们看看插入。直观地说，每个元素最多被推送和弹出一次，因此我们可以将昂贵插入的工作分散到更便宜的插入中。更正式地说，设势为 n，即堆栈上的元素数。每次进行插入时，都会进行一些弹出次数（例如 k），并且潜在增加 1 - k（添加一个新元素，删除 k）。然后摊销成本为 k + 1 + 1 - k，即 2。因此，insert 的摊销成本为 O(1)。

希望这可以帮助！

于 2014-05-29T17:54:00.013 回答
2

double是数据结构！在下面的方法中，ds表示正在对其执行操作的数据结构。

void Insert(ref double ds, double x)
{
    ds = x;
}

double FindMin(double ds)
{
    return ds;
}

观察数据结构状态的唯一方法是查询其最小元素( FindMin)。修改数据结构状态的唯一方法是设置其新的最小元素( Insert)。所以数据结构只是集合的最小元素。

于 2014-05-29T17:51:16.487 回答