首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 分别给出算法各部分的时间复杂度。
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 分别给出算法各部分的时间复杂度。
admin
2016-03-29
48
问题
线性表(a
1
,a
2
,a
3
,…,a
n
)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。
分别给出算法各部分的时间复杂度。
选项
答案
在利用折半查找的方法查找x的过程中时间复杂度为O(nlog
2
n);交换元素位置时的时间复杂度为O(1);当查找不成功时,插入元素时的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/O2Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
东欧国家的私有化方式一般有四种,其中波兰采取的主要方式是()
论述赫鲁晓夫改革的背景、主要内容及作用。
简述美国“柯立芝繁荣”的主要表现,分析其产生原因。
下列哪一项不是凯末尔世俗化改革的内容?()。
下列关于清朝军机处的叙述,不正确的是()。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
武昌起义是由哪个团体发动的?()
阅读史料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合
某工厂有一个仓库可以存放甲、乙两种零部件,甲零件可以存放m件,乙零件可以存放n件,车间A专门生产甲零件,每次1件,每生产1件存放进仓库1件;车间B专门生产零件乙,每次1件,每生产1件存放进仓库1件。总装车间每次从仓库取出2件甲零件、1件乙零件组装成成品,车
随机试题
关于权利登记制度,下列说法错误的是()。
住房和城乡建设部确认建筑信息化的最佳解决方案是以()技术为核心并作为中国未来建筑信息化的发展方向。
监理单位与项目法人之间是( )关系。
信汇凭证是信汇委托书,内容与电汇委托书相同,一般采用密押而不用手签。()
下列收入中不计入应纳税所得额的有()。
M国F汽车集团在经历了10余年的全面扩张之后,由于市场变化及公司竞争力下降,业绩全面下滑。集团进行了重大战略调整,即从战略扩张改为战略收缩,只专注于北美市场,专注于其自有的核心品牌。放弃旗下几个欧洲高端品牌,以改变该集团地域性品牌分割状态。对该公司而言,放
1999年7月,北京某中学教师14人参加某旅行社组织的云南旅游团。黄某为该团导游。时至出发日,黄某发现7位教师携带孩子同赴云南,即向旅行社报告并要求他们增交旅游费用。这7位教师增交了交通、餐旅费300元/人,但这7位教师坚持不另付门票钱,由此发生争执。一位
国泰民安是中国人历来的社会理想,而要长治久安就必须居安思危,因为“思所以危则安”。居安思危、思所以危则安是因为()
A、Themanwantstoobtainaninternationaldriver’slicensethathecanusebothintheU.S.andinhiscountry.B、Themanwant
A、SkiinCalifornia.B、Teachthemantoski.C、VisitherfriendsinEurope.D、Staywiththeman’sfamily.D男士说“你可以在我那里过圣诞节”,女士表示
最新回复
(
0
)