algorithm - 如何分析这段代码的复杂度？

Question

我正在解决 problem来自 codeforces。根据editorial ，下面代码的复杂度应该是O(n)。

for(int i = n - 1; i >= 0; --i) {
    r[i] = i + 1;
    while (r[i] < n && height[i] > height[r[i]])
        r[i] = r[r[i]];
    if (r[i] < n && height[i] == height[r[i]]) 
        r[i] = r[r[i]];
}

这里，height[i]是第i山的高度，r[i]是第一个右边的位置hill 高于 height[i]，height[0] 总是在高度数组的其他值中最大的。

我的问题是，尽管存在内部 while 循环，但我们如何保证代码的复杂度为 O(n)？

在内部 while 循环中，代码更新 r[i] 值直到 height[i] > height[r[i]]。更新的次数取决于高度数组。例如非降序排列的高度数组和非升序排列的高度数组的更新次数会有所不同。 (在这两种情况下，我们都会对数组进行排序，但 height[0] 除外，因为 height[0] 在此问题中应始终为最大值)。

有没有什么方法可以分析像这样随输入数据变化的算法？摊销分析将是答案之一？

附言。我想进一步澄清我的问题，我们要在循环中设置数组 r[]。那这个呢？如果数组 height = {5,4,1,2,3} 和 i=1, (r[2]=3, r[3]=4 因为 2 是第一个大于 1 的值，3 是第一个大于 2 的值)我们要比较 4 和 1，因为 4>1 ，我们不断尝试比较 4 和 2(=height[r[2]])，4 和 3(=height[r[3]])。在这种情况下，我们必须比较 4 次才能设置 r[1]。比较次数与 height = {5,1,2,3,4} 时不同。我们还能保证代码的复杂度是O(n)吗？如果我错过了什么，请告诉我。谢谢。

Answer 1

我用简单的例子尝试了提到的算法，但似乎没有任何改变，我是不是漏掉了什么？

示例:

n = 5
height = { 2, 4, 6, 8, 10 }
r = { 1, 2, 3, 4, 5 }

---- i:4 ----

r[4] < 5 ?

---- i:3 ----

8 > 10 ?
8 = 10 ?

---- i:2 ----

6 > 8 ?
6 = 8 ?

---- i:1 ----

4 > 6 ?
4 = 6 ?

---- i:0 ----

2 > 4 ?
2 = 4 ?

-------------

height = { 2, 4, 6, 8, 10 }
r = { 1, 2, 3, 4, 5 }