发现复杂的代码

与队列排队和出队操作一起考虑下面的操作，其中k是一个全球性的参数发现复杂的代码

MultiDequeue (Q) 
{ 
    m=k 
    while (Q is not empty) and (m > 0) 
    { 
    Dequeue (Q) 
    m = m −1 
    } 
}

什么是正队列操作的序列的最坏情况下的时间复杂度上最初是空队列？（A）Θ（n）（B）Θ（n + k）（C）Θ（nk）

它不是我的作业它在我的考试中被要求给我...... n根据我的说法应该是（n + k）。（n），因为while循环中有一个和条件，所以它依赖于n和k ....并且由于它不是嵌套循环或某个矩阵，它不是（nk）。 ...

我解决这种方式，如果同时（Q不为空）中的溶液，而不是同时有（Q不为空）和（M> 0），则时间复杂度将是（n）和如果m = 4它应该是n + k而不是nk .....它实际上是一个猜测

似乎GATE的问题... – 2013-02-14 01:39:24

lolz ...正确的不同教练机构正在告诉这个不同的答案和顺便说一句你如何是你的xam – 2013-02-14 01:43:33

我已经通过Mtech bt仍然出现它...没问题..！ – 2013-02-14 01:46:45

无论n排序的顺序是什么，Dequeue或MultiDequeue是原始O（1）操作的数量Enqueue/Dequeue can not超过2 * n。所以它是O（n）。

2013-02-14 02:06:33 glagolig

我同意。我想出了'k'总是无关紧要，因为它不会超出'n'。对于一个任意大的'k'和一个固定的'n'，则忽略'k-n'而只留下'n + n'，因此推断到最坏的2 * n，因此O（n）。 – WhozCraig 2013-02-14 04:49:33

-3

答案是C.在最坏的情况下，你会被执行n次排队操作。

2013-10-03 16:36:13 Samyak

该队列是空的初始的，所以while循环的条件永远不会成为真正的，所以时间复杂性将是西塔（N）。或者其他方式，如果只执行enquque和dequeue操作，那么它也将是theta（n）（n个插入和n个删除）。

2016-12-06 16:34:34

回答