首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。
admin
2009-02-15
44
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。
选项
A、O(n
2
)
B、O(nlog
2
n)
C、O(log
2
n)
2
D、O(n
2
log
2
n)
答案
A
解析
冒泡排序的过程是先将第1个数与第2个数相比较,若为逆序则交换两数,然后比较每两个数与第三个数,依此类推,直到第n-1个数与第n个数进行过比较为止。上述过程称为一趟冒泡排序,结果是最大的数被排在了最后。然后进行第二趟排序,对前面n-1个数进行冒泡排序,结果是次大的数被排到了n-1的位置上。一般来说,第i趟冒泡排序是从第一个数到第n-i+1的位置上,整个排序过程需进行A(1≤k≤n)趟。分析冒泡排序的效率,若初始序列为正序,则只进行一次排序。在排序过程中只进行n-1次比较,不交换数据。若为逆序,则需进行n-1趟排序,需进行n(n-1)/2次比较,交换数据的数量组也相同。因此,冒泡排序的复杂性是O(n
2
)。快速排序是对冒泡排序的一种改进,其基本思想是通过一趟排序将待排序的数据分成两部分,其中一部分的关键字均比另一部分的关键字小,然后再对这两部分分别进行快速排序,最后达到整个序列有序。因此,快速排序的复杂是O(nlog
2
n)。
转载请注明原文地址:https://kaotiyun.com/show/vJjZ777K
本试题收录于:
程序员上午基础知识考试题库软考初级分类
0
程序员上午基础知识考试
软考初级
相关试题推荐
假如某用户想登录FTP服务器,请根据说明把(1)、(2)与(3)填写完整,一般来说(4)的默认值是什么?在Windows的命令中,通过什么命令可打开FTP连接,当连接成功后通过什么命令可以把本地计算机的一个文件传到远程主机上?
假如某用户想登录FTP服务器,请根据说明把(1)、(2)与(3)填写完整,一般来说(4)的默认值是什么?为了方便使用者,一般提供了匿名FTP,一般以()作为登录的账号,通常只能下载文件,而无法上传文件。在Windows的命令中,其文件传输模式有哪两
请根据说明把图11-1中的(1)~(4)填写完整。使用SMTP时,其默认端口一般是多少,ICANN(因特网指派名字和号码公司)把一些常用的应用层程序固定使用的端口值一般设为多少?
安装Linux之前需要知道哪些必要的数据信息?使用Apache可实现虚拟主机服务,其中虚拟主机的含义是什么?
在安装Linux前,必须对硬盘进行分区。在Linux系统中用设备名称指定分区,命名方法是在驱动器的设备名称(/dev/hda或/dev/hdb)后加上指定分区的数字,1~4代表主分区,逻辑分区从5开始编号。若某系统使用两个IDE硬盘,第一个硬盘a分
该商务网站有一个购物车模块,购物车模块中自定义的两个Session属性如下。①CID用来记录用户选择的商品。②CNUM用来记录相应商品的数量。请根据表6-23所列的购物情况,将(1)~(3)空缺处对session对象处理方式的内容填
IEEE802.11定义了两种无线局域网(WLAN)的工作模式,根据图8-1所示的网络拓扑结构可知,该WLAN的工作模式是(1)。若该校园网采用IEEE802.11g标准部署相关区域的WLAN,则该无线区域的最大数据传输速率为(2)。1.A.Ad
阅读以下说明,回答问题1~问题3,把答案填写到答题纸的对应栏内。[说明]天网防火墙(SkyNet-FireWall)个人版(简称为天网防火墙)是一款由天网安全实验室制作的给个人电脑使用的网络安全程序。它根据系统管理者设定的安全规则(Security
阅读以下说明,回答问题1~问题3,把答案填写到答题纸的对应栏内。[说明]天网防火墙(SkyNet-FireWall)个人版(简称为天网防火墙)是一款由天网安全实验室制作的给个人电脑使用的网络安全程序。它根据系统管理者设定的安全规则(Security
在下列存储管理方案中,(16)是解决内存碎片问题的有效方法。虚拟存储器主要由(17)组成。
随机试题
用于表示“废水”的英文单词是sewage。
下列法院中,对第一审涉外民商事案件没有管辖权的是()
胃苓汤常用于治疗哪一型急性肾小球肾炎
患者,男,49岁。被诊断为肺叶肺不张。其典型的X线表现是
先兆子宫破裂的临床表现应除外
下列关于行政合同的表述,错误的是()。
教学过程的基本要素包括()
()的力量是无穷的,它对学生具有巨大的感染力和说服力,
A.条件(1)充分,但条件(2)不充分。B.条件(2)充分,但条件(1)不充分。C.条件(1)和(2)单独都不充分,但条件(1)和条件(2)联合起来充分。D.条件(1)充分,条件(2)也充分。E.条件(1)和(2)单独都不充分,条件(1)和条件(2
操作系统是()。
最新回复
(
0
)