设为首页 - 加入收藏
广告 1000x90
您的当前位置:黄大仙www78345 > 交换排序 > 正文

关于排序算法比较的问题

来源:未知 编辑:admin 时间:2019-06-16

  1.为什么书上分析时间复杂度主要是看比较次数得出的O(n^2) O(nlogn),交换也是得占时间的啊。

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  展开全部楼上的说法不准确吧,不能说比较和交换的次数不是一个级别的,交换也不是最多只有n次。比如一个逆序的数组进行升序的冒泡排序,交换就远远超过n次。

  但是假设比较次数为P(n),交换次数为Q(n),那么因为交换发生在比较之后(基本上排序算法都是这样,楼主可以自己想想),必然有Q(n)=P(n)。如果时间复杂度为T(n),那么显然根据时间复杂度的定义(极限定义),用大O表示法可以忽略Q(n)项(或用P(n)代替Q(n)),仅用P对T进行表示。

  因为大O表示法是对时间复杂度上限的一个估计,而这种每比较一次就需要交换的情况确实存在(最差情况),所以在T(n)中使用P(n)对Q(n)进行替换并不会扩大对上限估计,而只是乘以了系数2,在大O表示法中常数项是不写入的。

  这些数学分析一般在国内的算法教材中都不写入的,MIT的《ITA》注重这方面的叙述。

  这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡: 复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。

  快速排序:平均时间复杂度log2(n)*n,所有内部排序方法中最高好的,大多数情况下总是最好的。

本文链接:http://apkhealth.com/jiaohuanpaixu/357.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top