stack - 堆栈迭代的时间复杂度

Question

我有一个对象数组，我有两个堆栈，我遍历数组，对于每个元素，我推送以前的对象（从堆栈 1 弹出并推送到堆栈 2），然后重新放置它们（从堆栈 2 弹出并推送到堆栈 1 ）。

我想知道它是什么时间复杂化 - o(n) 或 o(n^2)

因为每个堆栈操作（push pop）都是o（1）。

 for (int i = 0; i < buildingsHeight.Length; i++)
            {
            
                while (!BuildingStack.IsEmpty() && !didWeFoundHigerBuilding)
                {
                   
                    BuildingStackNode buildingInLine = BuildingStack.Pop();
                    
                    helperStack.Push(BuildingStack.Pop());
                }

                // restore data 
                while (!helperStack.IsEmpty())
                {
                    BuildingStack.Push(helperStack.Pop());
                }
}

标签： stacktime-complexity

Answer 1

首先，我想您的意思是“O”而不是小“o”（具有不同的含义）？其次，如果不定义“n”，就说像 O(n) 这样的东西没有任何意义。那么什么是n？

您显示的代码有点奇怪，因为您正在循环数组buildingsHeight，但您没有对循环内的数组执行任何操作。无论如何，这段代码的时间复杂度取决于两个参数：长度和项目buildingsHeight a数量（假设最初是空的）。bBuildingStackhelperStack

while 循环各取O(b)，而 for 循环迭代a次数，因此整体复杂度为O(ab)。