具有某些操作的双向链表

Question

对于具有数字元素的双向链表Q，并且我们有一个指向第一个和最后一个元素的指针，我们定义了两个操作。

Delete (k): delete k first elements from Q.
Append (c), check the last element from `Q`, if this value  bigger than c, delete this elements and repeat it again until the last element is lower or equal to `c` (or empty `Q`), then insert c as last elements of Q`.` 

如果我们在空列表Q上以任意顺序重复这两个操作的序列n次，则这些操作的所有成本的总和接近2n。 为什么我的导师会联系2n？ 任何提示或想法都值得赞赏。

Answer 1

当我们"在空列表 Q 上以任意顺序重复Delete和Append n 次"时，Append 被称为 n 次;因此n执行列表元素插入。

由于列表最初是空的，因此它永远不会包含超过 n 个元素;因此最多n列表元素删除是以 Delete 和 Append 的组合执行的。

因此，每个Delete和Append中的循环总数(包括Append中的读取(不超过2 n。

总而言之，程序的任何部分的执行次数都没有超过 2 n次(单独计算列表元素插入、列表元素删除和列表元素访问可能常见的代码(。

当k始终为 0 且c不减少(包括始终为 0(时，成本最小：我们有n列表元素插入、n列表元素读取(一个返回空(、n空度测试、n-1元素比较和不删除。因此，成本随参数变化很大。

注：">这些操作的所有成本之和接近2 n"定义不明确，因此甚至没有错。更糟糕的是，如果列表元素删除，运气不好(例如代码缓存未命中，调试代码......(比其他元素慢得多，则可能是代码持续时间根据参数变化很大(远高于 2(。因此，对于任何虱子的含义，执行时间并不总是">大约 2 n"。

更新：在评论中，我们被告知列表元素插入和删除具有相同的成本 1.列表元素插入次数n，列表元素删除次数介于 0 到 n 之间。因此，如果我们忽略其他成本(这是合理的，内存分配成本占主导地位(，总成本约为 n 到 2 n，具体取决于参数。此外，对于许多参数(包括 k>=1 大多数时间(，列表元素删除几乎n，因此如果坚持最佳猜测，例如在多项选择题中，成本约为 2 n (a( n + k (b( n (c( 2 n (d( 3 n作为唯一的选项。

Answer 2

如果我们在空上以任意顺序重复这些操作 n 次 列出这些操作的所有成本的Q总和接近2n

它实际上是O(n)，因为我们知道列表Q是空的。

DoStuff(list Q, int n):
    for(int i = 0; i < n; i++)
        Q.Delete(k) //O(k)
        Q.Append(c) //O(sizeof(Q))
        //or
        //Q.Append(c) //O(sizeof(Q))
        //Q.Delete(k) //O(k)

其中n是迭代次数。

现在假设列表不为空，那么我们将有O(n*(sizeof(Q)+k)).对此的解释如下：

假设Delete (k)最糟糕的情况是从k大小为 Q 的Q中删除 k 个第一个元素，然后我们将删除 n 个元素。但是，说O(k)更准确，因为您将始终仅删除前k元素。

假设Append (c)的最坏情况是Q中的所有元素都大于c的值。这将从尾节点开始，并从Q中删除所有节点。按任一顺序

Delete(k) //O(k)
Append(c) //O(sizeof(Q))

或

Append(c) //O(sizeof(Q))
Delete(k) //O(k)

更

糟糕的情况是，只有这两个命令是O(sizeof(Q)+k). 现在我们知道我们必须n迭代来做到这一点，所以我们终于得到了O(n*(sizeof(Q)+k))

至于你教授说的，我能想象你的教授这么说2n的唯一原因是因为n次调用了2函数。因此2n.