这段代码的复杂度是多少?(大O)那是线性的吗? [英] What is complexity of this code? (Big O) Is that linear?

查看:20
本文介绍了这段代码的复杂度是多少?(大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).

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)那是线性的吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆