如何分析这段代码的复杂性？

我正在从代码解决problem。根据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]是第一右山比height[i]更高的位置，并且是height[0]高度阵列的其它值中的最大的总。

我的问题是，我们如何保证代码的复杂性是O（n），虽然内部while循环的存在？

在inner while循环中，代码更新r[i]值，直到height[i]>height[r[i]]。并且更新的数量取决于高度数组。例如，按非递减顺序排列的高度数组的更新次数将与按非递增顺序排列的高度数组的排列次数不同。（在这两种情况下，我们将排列除height[0]之外的数组，因为height[0]在此问题中应始终为最大值）。

是否有任何方法来分析这样的输入数据变化的算法？摊销分析将是答案之一？

PS。我想更多地阐明我的问题，我们要在循环中设置数组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）吗？如果我错过了什么，请让我知道。谢谢。

来源

2013-05-29 MS.Kim

我用简单的例子试过了上面提到的算法，但似乎没有改变，我错过了什么吗？

例子：

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-29 08:59:09

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

你可以用这样的方法，其中将返回的时间数它的内部循环被执行检验这一假设：平均情况

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

有了这个，你就可以检查最坏的情况下，等。

来源

2013-05-29 11:41:27 sowrov

如何分析这段代码的复杂性？

回答

相关问题