选择排序时间复杂度
1个回答
展开全部
选择排序时间复杂度:选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的位置已经是正确的了。
选择排序:
长度为N的数组
1)看0~N-1;看N次;(第一个与第一个比较,选择最小值;第二个和最小值比较,以此类推)比较N次,交换一次;
结果:最小的放到第一位上;
2)看1~N-1:看N-1次;比较N-1次;交换一次;
结果;最小的放到第二位;
3)以此类推直至最后一次,全部比较完成;
时间复杂度为:
看:N+(N-1)+(N-2)+······+1
比较:N+(N-1)+(N-2)+······+1
交换:N
求和为一个二次型多项式,因为等差数列求和会出现二次型;
最终时间复杂度为O(N²)
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询