算法的渐近复杂性

问题描述

我想知道在使用Big-theta表示法的以下算法中，此过程可以返回的最小值和最大值是多少。算法为：

procedure F(𝐴[1..n])
   s = 0
   for i = 1 to n
      j = min(max(i,A[i]),n³) 
      s = s + j
   return s

推荐答案

编辑：删除了原始答案，因为它回答了错误的问题。

分析取决于以下行：

min(max(i,A[i]),n³) 

如果我们找出了这一点的案例，那么我们就可以很容易地计算出结果的案例。我们必须回答i > A[i]，然后i和A[i]中的较大者是否大于n^3。

1. i > A[i]和i > n^3。不可能是这种情况，因为i <= n和i, n是整数。
2. i > A[i]和i < n^3。例如，如果A[i] = -1，则可能发生这种情况。在本例中，我们将i与0 <= i <= n相加。结果是n(n+1)/2，即O(n^2)。(我使用O，但Theta也适用)。
3. i < A[i]和A[i] < n^3。如果i + 1<= A[i] <= n^3 - 1和n > 2，则可能发生这种情况。在本例中，我们将i + 1和n相加，对于i等于1到n，或者将n^3 - 1和n相加。在低端我们得到n(n-1)/2 - n，就像以前用-n表示-1一样，在高端我们得到n^4 - n；介于O(n^2)和O(n^4)之间。
4. i < A[i]和A[i] > n^3。如果A[i] > n^3，则可能发生这种情况。在本例中，n^4、O(n^4)的n^3和n时间合计。

基于以上，我的想法是最好情况的下界是Omega(n^2)，最坏情况的上界是O(n^4)。这两个界限对于各自的情况都是严格的，但由于它们不同，我们不能为结果的增长率给出一个严格的界限。

这篇关于算法的渐近复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！