堆栈和队列复杂度

Question

def sumarray(a)
    q = Queue.new
    for i in 0..(a.length-1)
        q.enqueue(a[i])
    end
    sum = 0
    while q.length > 0
        sum = sum + q.dequeue
    end
    return sum
end

假设上述算法中使用的队列实现：

入队操作是 O(1) 出队操作是 O(k)，其中 k 是当前在队列中的元素数考虑到队列操作，上述sumarray算法的整体复杂度是多少？

谁能解释一下复杂度是如何推导出来的？谢谢！

Answer 1

很明显，第一个循环是 O(n)，其中 n=a.length

for i in 0..(a.length-1)
    q.enqueue(a[i])
end

第二个循环执行 n 次，q.dequeue 是 O(n) 所以我们得到 O(n²)

while q.length > 0
    sum = sum + q.dequeue
end

所以整体复杂度是O(n²)

中最差的

现在您可能会说，由于 q 每次迭代都变得越来越小，所以这个论点过于简单化了。因此，让我们总结所有 q.dequeue 复杂性。

O(n) + O(n-1) + O(n-2) + O(n-3) ... O(1)

这看起来像三角数序列吗？所以我们知道公式

n + (n-1) + (n-1) + ... + 1 = n*(n+1)/2

或

(n*n + n) / 2

舍弃常数因子，低阶复杂度留下 n*n

堆栈和队列复杂度

Stack & queue complexity

ruby

queue

complexity-theory

stack