这个堆栈的复杂性

Question

给定的 Stack 解 = n^2 不是定义了复杂度吗？

Codechef Editorial Link

因为，外循环是1:N 弹出操作也是 O(N-1) ~= O(N) （最坏情况）... 所以这不是N^2吗？

Answer 1

没有。可以这样想：每个厨师最多 一次 被推入堆栈，并且最多也被弹出一次。由于您只遍历列表一次，堆栈操作的数量以 2N 为界，即时间复杂度 = O(N)。