问题描述
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).
I think the code sorts the input array and that its worst case complexity is O(n).
这段代码正确的 big-O 复杂度是多少?
What is the correct big-O complexity of this code?
推荐答案
O(n^3),这是冒泡排序的低效版本.
It's O(n^3), and it's an inefficient version of bubble sort.
代码扫描数组,寻找第一对相邻的乱序元素,交换它们,然后从数组的开头重新开始.
The code scans through the array looking for the first adjacent pair of out-of-order elements, swaps them, and then restarts from the beginning of the array.
在最坏的情况下,当数组逆序时,代码满足的递推关系为:
In the worst case, when the array is in reverse order, the recurrence relation the code satisfies is:
T(n+1) = T(n) + n(n-1)/2
那是因为在代码到达第 n+1 个元素之前,算法会对前 n 个元素进行排序.然后代码反复向前扫描以找到这个新元素,并将其向后移动一个空格.这需要时间 n + (n-1) + ... + 1 = n(n-1)/2.
That's because the first n elements will be sorted by the algorithm before the code reaches the n+1'th element. Then the code repeatedly scans forward to find this new element, and moves it one space back. That takes time n + (n-1) + ... + 1 = n(n-1)/2.
求解为 Theta(n^3).
That solves to Theta(n^3).
这篇关于这段代码的复杂度是多少?(大O)那是线性的吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!