1

I am solving a problem from codeforces. According to the editorial, the complexity of the following code should be 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]];
}

Here, height[i] is the height of i-th hill and r[i] is the position of the first right hill which is higher than height[i], and height[0] is the always greatest among other values of height array.

My question is, how we can guarantee the complexity of the code to be O(n) although the inner while loop's being?

In the inner while loop, the code updates r[i] values until height[i] > height[r[i]]. and the number of the updates depends on height array. For example, the number of updates of the height array sorted by non-decreasing order will be different from that of the height array sorted by non-increasing order. (in both cases, the we will sort the array except height[0], because height[0] should be always maximum in this problem).

And Is there any method to analyze an algorithm which varies on input data like this? amortized analysis will be one of answers?

PS. I would like to clarify my question more, We are to set the array r[] in the loop. And what about this? if the array height = {5,4,1,2,3} and i=1, (r[2]=3, r[3]=4 because 2 is the first value which is greater than 1, and 3 is the first value which is greater than 2) we are to compare 4 with 1, and because 4>1, we keep trying to compare 4 and 2(=height[r[2]]), 4 with 3(=height[r[3]]). In this case we have to compare 4 times to set r[1]. The number of comparison is differ from when height = {5,1,2,3,4}. Can we still guarantee the complexity of the code to be O(n)? If I miss something, Please let me know. Thank you.

4

2 回答 2

0

我用简单的例子尝试了上述算法，但似乎没有任何改变，我错过了什么吗？

例子：

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 }
于 2013-05-29T08:59:09.467 回答
0

你的算法（我不知道它是否能解决你的问题）实际上是 O(n)，即使有一个内部循环，但在大多数情况下，由于给定的条件，内部循环不会执行。所以在最坏的情况下，它会像2n时间一样运行，即 O(n)。

您可以使用这样的方法测试此假设，其中yourMethod将返回其内部循环执行的次数：

   int arr[] = {1, 2, 3, 4, 5};
    do {
        int count = yourMethod(arr, 5);
    }while(next_permutation(arr, arr+5));

有了这个，您将能够检查最坏情况、平均情况等。

于 2013-05-29T11:41:27.930 回答