Стек и очередь сложность,

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 

Предположим, что реализация очереди используется в приведенном выше алгоритме:

операции Enqueue представляет собой О (1) операции Dequeue представляет собой О (к), где к есть число элементов в настоящее время очередь Принимая во внимание операции очереди, какова общая сложность алгоритма для sumarray?

Может кто-нибудь объяснить, как сложность получается? Благодаря!

Answer 1

Это, надеюсь, очевидно, что это первый цикл О (п), где п = a.length

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

Второй цикл выполняется n раз, и q.dequeue О (п) так, что дает нам O (п)

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

Таким образом, общая сложность является худшим из тех, что о (п)

Теперь вы можете сказать, что с 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