我有算法的作业，有以下问题：
给定队列 Q 和方法：
queue(Q, x) //inserts x to the queue from left ，
dequeue(Q) //returns most right element of Q和
multiqueue(Q, k) //runs dequeue(Q) k times ，
如何证明 n 个操作最多需要以空列表开头的 O(n( 步？
正如我从您的评论中看到的那样，您几乎回答了您的问题。
- 正如您所解释的，队列为 O(1(
- 正如您所解释的，取消排队是 O(1(
棘手的是，定义 multidequeue(Q， k( 的 k 小于队列中的元素数量。
我们假设队列开始时为空，这就是为什么您可以假设总是为 O(n( 的复杂性调用多取消队列，我将解释：
如果你调用多排 n 次，这意味着你没有使用其他操作包括队列，这就是为什么你没有任何元素可以取消排队，因此你的 k 是一个真正的常量。
假设您调用队列 n-1 次，您只能调用一次多排队列，因为您已经花费了所有其他 n - 1 个操作。
这就是为什么 O(num_of_times_calling_multidequeue * multidequeue( = O(n(
正如@gefen keinan指出的那样，我是这样解决的：
假设我们有一个空的队列 Q 和 n 个可用操作。 我们知道 queue(( 和 dequeue(( 都有 O(1( 的复杂性。"最坏的情况"是操作 row(( 的 n - 1 倍，然后有参数 k 为 n - 1 的 multidequeue(k(，因为如果我们更频繁地使用它，它只会返回错误。
有了这些知识，我们可以得出结论，拥有 (n-1(*O(1( + (n - 1( * O(n( = O(2n( = O(n(。
谢谢大家的回答。