首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。
admin
2009-02-15
87
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(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
程序员上午基础知识考试
软考初级
相关试题推荐
请把下面(n)处填写完整。Internet上的每台主机和路由器都有一个IP地址,IP地址包含网络号和主机号,而为支持了子网,路由器需要一个子网掩码,它代表了“网络+子网号”与主机号之间的分割方案,如:192.168.65.0/24"表示子网掩码有
打开OutlookExpress后,在出现的主窗口中靠左边有一子窗口是“文件夹列表”,请列出其中包括的5个文件夹(用户自建的文件夹不计入)。若发件人使用MIME格式发送邮件,而收件人客户端程序不支持MIME格式,致使收件人无法打开邮件所携带的附件。
IIS6.0安装的硬盘分区最好选用NTFS格式,是因为(1)和(2)。(1)、(2)备选答案:A.可以防止网页中的Applet程序访问硬盘中的文件B.可以针对某个文件或文件夹给不同的用户分配不同的权限C.可以使用系统自带的文件加
请填写图1-3中PC1的相应参数。IP地址:(1):子网掩码:(2);默认网关:(3);以太网接口的MAC地址:(4)。图1-3表明,在默认情况下该数据包请求的服务为(8)。
阅读以下说明,回答问题1至问题4,将解答填入对应的解答栏内。[说明]某公司拥有一个C类地址块212.253.115.0/24,网络拓扑结构如图1-1所示。在PCI的DOS命令窗口中,运行atp-a命令显示PCI的ARP缓存,得到结
阅读以下技术说明,根据要求回答问题。[说明]某公司A楼有40层,每层高3.3m,同一楼层内任意两个房间最远传输距离不超过90m,A楼和B楼之间距离为500m,需在整个大楼进行综合布线,结构如图2-34所示。为满足公司业务发展的需要,要求为
IEEE802.11定义了两种无线局域网(WLAN)的工作模式,根据图8-1所示的网络拓扑结构可知,该WLAN的工作模式是(1)。若该校园网采用IEEE802.11g标准部署相关区域的WLAN,则该无线区域的最大数据传输速率为(2)。1.A.Ad
阅读以下说明,回答问题1~问题3,把答案填写到答题纸的对应栏内。[说明]天网防火墙(SkyNet-FireWall)个人版(简称为天网防火墙)是一款由天网安全实验室制作的给个人电脑使用的网络安全程序。它根据系统管理者设定的安全规则(Security
RPC1757文件定义的RMON管理信息库是对MIB-2的扩充,其中的矩阵级存储的信息是(58)的通信情况。
随机试题
国际货币基金组织的职能有________、________、________、________、________。
夸美纽斯在《大教学论》中提出了()。
一项研究表明,那些在舒适环境里工作的人比在不舒适环境里工作的人生产效率高25%。评价工作绩效的客观标准包括承办工件数和工件的复杂程度。这表明:日益改善的工作环境可以提高工人的生产效率。以下哪项为真,最能削弱上述结论?()
甲于1992年3月5日犯A罪,该罪的法定最高刑为10年,1996年11月21日甲又犯B罪,B罪的法定最高刑为7年,那么A罪的追诉期限的结束时间应为()。
What’saman?Or,indeed,awoman?Biologically,theanswermightseemobvious.Ahumanbeingisa(n)【C1】______whohasgrownfr
若没有特殊声明,匿名FTP服务登录口令为()。
In1995about700,000robotswereoperatingintheindustrializedworld.Over500,000wereusedinJapan,about120,000inWe
NOTJUSTASHOP!Inhisyearlyreport,theChairmanofachainofretailoutletswritesaboutthefinancialaspectsofthe
TheLondonCentreForyourmeeting,productlaunch,specialeventPurpose-builtroomsLatestpresentationtechnologyFirst-class
A、Neitherofthemlikethewriter.B、BothofthemlikeEllaFitzgerald.C、Oneofthemiscrazyaboutwriting.D、ThemanlikesFi
最新回复
(
0
)