为什么这个 For 循环的时间复杂度是 O(N)？

Question

有没有办法从直觉或证明中理解为什么以下的时间复杂度是 O(N)？

它的作用基本上是给定一个整数的输入，我们在进行反向扫描array时创建firstSmallLeft相同长度的数组 where firstSmallLeft[i]= 第一个索引 where array[index]< 。（即，对于索引 i，它从 i-1, ... , j 扫描，直到找到第一个较小的元素，使得 array[j] < array[i]）array[i]

例如，如果输入 = [3,2,5,6,4,1].
firstSmallLeft 会是[-1,-1,1,2,1,-1]

//input int[] array
int[] firstSmallLeft = new int[array.length];
firstSmallLeft[0] = -1;
for(int i = 1; i < array.length; i ++){
    int cur = i -1;
    while (cur >=0 && array[cur] >= array[i]){
        cur = firstSmallLeft[cur];
    }

    firstSmallLeft[i] = cur;
}

Answer 1

一个重要的见解是，firstSmallLeft接收到值的最后一个条目（在索引处i-1）代表堆栈的顶部，该堆栈以链接列表的形式实现。中的条目firstSmallLeft表示一个输入值（因为它出现的索引是 input 中的索引array）和链表中的一个链接（因为它的值是 中的索引firstSmallLeft）。堆栈中的底部元素具有空链接 (-1)。

一般来说，并非所有元素都firstSmallLeft在表示的堆栈中，因为某些索引被跳过。一个例子：

假设栈顶位于索引 100（当i为 101 时），其值为 40，firstSmallLeft[40]为 -1，那么这意味着我们的栈只有两个元素（array[100]和array[40]），而没有其他元素in 的索引firstSmallLeft包含在当前堆栈中。其中每一个都曾经位于堆栈中，但后来已从堆栈中弹出。

每次cur = firstSmallLeft[cur];执行时（在内循环中），我们实际上会弹出堆栈中的一个元素（起始的链表cur短一个元素）。

当我们这样做时，firstSmallLeft[i] = cur我们会压array[i]入堆栈，并引用我们想要保留的堆栈部分。

现在这个“虚拟”堆栈已被识别，我们看到以下内容：

一个值只会被压入堆栈一次，并且只能从堆栈中弹出一次，之后就不会再被访问。

再次计算表达式while以发现我们需要退出循环的开销，发生的次数与外循环迭代的次数相同（即n-1次数）

因此该算法是O(n)。