#stack #time-complexity
#стек #временная сложность
Вопрос:
У меня есть массив объектов, и у меня есть два стека, я перебираю массив и для каждого элемента выталкиваю предыдущие объекты (извлекаю из стека 1 и перемещаю в стек 2), а затем повторно удаляю их (извлекаю из стека 2 и перемещаю в стек 1).
Интересно, какое это время — o (n) или o (n ^ 2)
потому что каждая операция стека (push pop) равна o (1).
for (int i = 0; i < buildingsHeight.Length; i )
{
while (!BuildingStack.IsEmpty() amp;amp; !didWeFoundHigerBuilding)
{
BuildingStackNode buildingInLine = BuildingStack.Pop();
helperStack.Push(BuildingStack.Pop());
}
// restore data
while (!helperStack.IsEmpty())
{
BuildingStack.Push(helperStack.Pop());
}
}
Ответ №1:
Прежде всего, я полагаю, вы имеете в виду «O», а не маленькую «o» (что имеет другое значение)? Во-вторых, говорить что-то вроде O (n) не имеет никакого смысла без определения «n». Итак, что такое n?
Код, который вы показали, немного странный в том смысле, что вы перебираете массив buildingsHeight
, но ничего не делаете с массивом внутри цикла. В любом случае, временная сложность этого фрагмента кода зависит от двух параметров: длины buildingsHeight
a
и количества b
элементов в BuildingStack
(при условии, что helperStack
изначально пусто).
Каждый цикл while выполняется O(b)
, а цикл for повторяется a
несколько раз, поэтому общая сложность такова O(ab)
.