选择排序时间复杂度

 我来答
娱乐学习官
2022-10-08 · TA获得超过275个赞
知道小有建树答主
回答量:1487
采纳率:100%
帮助的人:23.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²)

推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式