刚才见到求职板块一哥们的笔试题中有个冒泡排序的时间复杂度的问题,他写的是O(n*n)。
由于我今天刚刚闲来无聊写着玩写了一个冒泡排序,便仔细想了一下。可是得到的答案却不一样。我觉得冒泡排序的时间复杂度应该是O(n!)。不知到大家怎么看。我写的冒泡排序算法如下:
Integer[] numbers={5,15,3,23,25,28,16,4,15,17,33};
for(int i=0;i<numbers.length;i++)
{
for(int j=i+1;j<numbers.length;j++)
{
if(numbers[i]>numbers[j])
{
Integer temp=numbers[i];
numbers[i]=numbers[j];
numbers[j]=temp;
}
}
}
for(int k=0;k<numbers.length;k++)
{
System.out.print(numbers[k]+" ");
}
按照比较次数来看:
i=0 n 次
i=1 n-1
i=2 n-2
。。。
也就是 1,2,3,4,...n
计算得 n(1+n)/2 数量级为 n*n
[quote]他写的是O(n*n)。 [/quote]
这个是正确答案,再仔细好好分析下。