算法渐近复杂度

Question

我想知道这个过程在以下算法中使用 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

Answer 1

编辑:删除了原始答案，因为它是针对错误问题的。

分析取决于以下行:

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^3求和n n^4 的次数, O(n^4) .

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