algorithm - 带有一些操作的双向链表

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.

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

当 k 始终为 0 且 c 非递减(包括始终为 0)时，成本最小:我们有 n 列表元素插入、n 列表元素读取(一个返回空)、n 空性测试、n-1 元素比较和无删除。因此，成本随参数的不同而显着变化。

注意:“ 这些操作的所有成本总和接近 2n”是未定义的，因此甚至没有错。更糟糕的是，如果列表元素删除，由于一些坏运气(例如代码缓存未命中，调试代码......)比其余的慢得多，可能是代码持续时间因参数而异(远高于 2) .因此，执行时间不是 总是“ 大约 2n”，因为它有任何不合理的含义。

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