java - 如何分析以下算法复杂度

Question

这个问题已经有答案了:

What is time complexity and how to find it? [duplicate] (2 个回答)

What is complexity of this code? (Big O) Is that linear? (1 个回答)

已关闭 3 年前。

我是算法分析的新手，所以如果有人能帮助我，我将不胜感激。我有以下用于对数组进行排序的算法:

for(int i = 0 ; i < list ; i++){
    if(list[i] > list[i+1]){
       swap list[i] with list[i+1]
       i = -1;
    }
}

我声称这个算法是线性算法(即 O(n))，但我不知道如何证明这一点。

我很感激任何帮助。提前致谢。

Answer 1

在最坏的情况下，该算法实际上是三次的(O(n^3)，其中 n = 列表的长度)。想象一下以下输入:list = [5,4,3,2,1]。

第一次迭代:列表[0] > 列表[1]。进行交换使得 list = [4,5,3,2,1]，并且 i 减少到 -1，因此循环重新开始。

第二次迭代: list[0] < list[1]。

第三次迭代:列表[1] > 列表[2]。进行交换使得 list = [4,3,5,2,1]，并且 i 减少到 -1，因此循环重新开始。

第四次迭代:列表[0] > 列表[1]。进行交换使得 list = [3,4,5,2,1]，并且 i 减少到 -1，因此循环重新开始。

同样的模式继续:我们将需要 6 次以上的迭代才能将 2 带到列表的开头，10 次迭代才能将 1 带到列表的开头，并且在列表全部排序后需要 5 次迭代来浏览列表。总共4+6+10+5=25，即5^2。那么为什么是 n^3 而不是 n^2？

直觉:

对于像上例中那样反向排序的列表，我们需要将每个元素从最大到最小放置到列表的头部。初始列表中的第 j 个元素是总体中第 j 个最大的元素，需要 (1+2+...+j)=O(j^2) 步骤才能到达列表的头部。因此，为了反转长度为 n 的列表，我们大约需要 (1^2 + 2^2 + ... + n^2) 个步骤。这是从 1 到 n 的平方和，即 O(n^3) - 如果您不知道为什么，这是一个非常著名的算术公式:sum of squares.

免责声明:当然，它不会完全是 n^3 步，但大约是这样(这毕竟是 Big-O 表示法的定义。n 越大，它就越接近 n^3 )。