Блог

У меня есть массив объектов, и у меня есть два стека, я перебираю массив и для каждого элемента выталкиваю предыдущие объекты (извлекаю из стека 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());
                }
}
 

Прежде всего, я полагаю, вы имеете в виду «O», а не маленькую «o» (что имеет другое значение)? Во-вторых, говорить что-то вроде O (n) не имеет никакого смысла без определения «n». Итак, что такое n?

Код, который вы показали, немного странный в том смысле, что вы перебираете массив buildingsHeight , но ничего не делаете с массивом внутри цикла. В любом случае, временная сложность этого фрагмента кода зависит от двух параметров: длины buildingsHeight a и количества b элементов в BuildingStack (при условии, что helperStack изначально пусто).

Каждый цикл while выполняется O(b) , а цикл for повторяется a несколько раз, поэтому общая сложность такова O(ab) .