问算法的渐近复杂度

EN

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

分析取决于以下几行：

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

如果我们找出了这种情况，那么我们就可以很容易地计算出结果的情况。我们必须回答是否i > A[i]，然后i和A[i]的大小是否大于n^3。

1. i > A[i]和i > n^3。因为integers.
2. i > A[i]和i, n分别是integers.
3. i > A[i]和i, n，所以不会出现这种情况。例如，如果是A[i] = -1，就会发生这种情况。在本例中，我们将为0 <= i <= n添加i。这是n(n+1)/2，也就是O(n^2)。(我使用Theta，但Theta应用为well).
4. 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).
5. i < A[i]和A[i] > n^3之间。如果使用A[i] > n^3，就会发生这种情况。在本例中，我们有O(n^4).

、n^3和n的n^4时间总和

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