这段代码的复杂度是多少？ （大O）这是线性的吗？

for(int i=0; i<array.length -1; i++){
  if(array[i] > array[i+1]){
    int temp = array[i];
    array[i] = array[i+1];
    array[i+1]=temp;
    i=-1;
  } 
}

我认为代码对输入数组进行排序，最坏情况的复杂度是 O(n)。

该代码的正确大 O 复杂度是多少？

它的时间复杂度为 O(n^3)，并且是冒泡排序的低效版本。

该代码扫描数组，查找第一对相邻的无序元素，交换它们，然后从数组的开头重新开始。

最坏的情况下，当数组逆序时，代码满足的递推关系为：

 T(n+1) = T(n) + n(n-1)/2

这是因为在代码到达第 n+1 个元素之前，算法将对前 n 个元素进行排序。然后代码重复向前扫描以找到这个新元素，并将其向后移动一个空格。这需要时间 n + (n-1) + ... + 1 = n(n-1)/2。

解出 Theta(n^3)。