如何分析以下算法复杂度[重复]

Question

我是新的算法分析，所以如果有人能帮助我，我很感激。我有以下排序数组的算法：

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]。

第一次迭代:List[0]>List[1]。进行交换时，list=[4,5,3,2,1]和i被简化为-1，因此循环重新开始。

第二次迭代:List[0]

第三次迭代:List[1]>List[2]。进行交换时，list=[4,3,5,2,1]和i被简化为-1，因此循环重新开始。

第四次迭代:List[0]>List[1]。进行交换时，list=[3,4,5,2,1]和i被简化为-1，因此循环重新开始。

同样的模式还在继续：我们将需要更多的6次迭代来将2放到列表的开头，对1进行10次迭代，并在列表全部排序后浏览5次。4+6+10+5=25，等于5^2。那么为什么是N^3而不是N^2呢？

免责声明：当然，它不会完全是n^3步，但它将大致如此（这毕竟是大O符号的定义，n越大，它将越接近n^3）。