Система обозначений Big-O: каков порядок алгоритма?

У меня проблемы с пониманием обозначения Big-O. Вот алгоритм, который я написал. Предполагается, что он является альтернативой функции (C ++) Stack’s size (), и мне нужно определить время ее работы, исходя из предположения, что N элементы в стеке, когда он вызывается.

Algorithm size():
Input: none
Output: A constant value of the size of an n-element stack.
Let V be a vector of n type objects.
Let S be the name of the stack that is being operated on by this function.
K ← 0
V
while !empty()
V.push_back(top())      //Keep track of elements in V
S.pop()             //Remove element from stack
K ← K + 1           //Count the size of the stack
return K                //Return the size of the stack
for i ← K – 1, i > 0, i-- do
S.push(V[i])            //Retain initial contents of stack

Пожалуйста, поправьте меня, где я не прав:

  • В строке K ← 0 я думаю, что это операция O (1).

  • Создание вектора V также является операцией O (1).

  • цикл while является операцией O (n), поскольку выполняется до тех пор, пока не очистит стек, содержащий N содержание.

  • Возвращение значений обратно в V является операцией O (n).

  • Удаление содержимого из стека S является операцией O (n).

  • Возвращение K является операцией O (1).

  • Цикл for является операцией O (n).

  • Задать содержимое обратно в S — это операция O (n).

-4

Решение

Операции push и pop — это O (1). Цикл for, который содержит push, равен O (n), а push — O (1).

MIT всегда готовит хорошие вещи для учебы http://web.mit.edu/16.070/www/lecture/big_o.pdf.

1

Другие решения