下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是

admin2019-04-24 53

问题下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是

选项 A、在顺序存储的线性表中寻找最大项
B、在顺序存储的线性表中进行顺序查找
C、在顺序存储的有序表中进行对分查找
D、在链式存储的有序表中进行查找

答案A

解析最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何情况更长。
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。在输入不同的情况下算法的运行时间复杂度可能会发生变化。平均时间复杂度给出了算法的期望运行时间，有助于算法好坏的评价以及在不同算法之间比较时有一个统一标准。
在顺序存储的线性表中寻找最大项，其平均情况与最坏情况下的时间复杂度都是n/2。

转载请注明原文地址:https://www.kaotiyun.com/show/cURp777K

本试题收录于：二级C语言题库NCRE全国计算机二级分类

二级C语言

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是

二级C语言

NCRE全国计算机二级

下列特征中不是面向对象方法的主要特征的是()。

一个工作人员可以使用多台计算机，而一台计算机可被多个人使用，则实体工作人员与实体计算机之间的联系是()。【10年9月】

设有定义：inta=1，b=2，c=3；以下语句中执行效果与其它三个不同的是

下列选项中，能够满足’’只要字符串s1等于字符串s2，则执行ST’’要求的是

设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（）。

在E-R图中，用来表示实体联系的图形是（）。

一个工作人员可使用多台计算机，而一台计算机被多个人使用，则实体工作人员与实体计算机之间的联系是（）。

将E-R图转换为关系模式时，E-R图中的实体和联系都可以表示为（）。

任何社会的制度安排一方面应普遍适合社会每一位成员，另一方面又要使社会底层的人们获得最大的利益，不应出现强者剥夺弱者而使弱者更弱的状况，这属于()

测试用例

骨髓增生异常综合征患者的骨髓幼稚细胞中有Auer小体可见于

以下属于非法人组织的有:()。

贝克和雷米认知疗法的基本步骤包括()。

许多人喜欢晨练，但从环境角度来看，城市早晨的空气并不新鲜，原因是()。

设a＞0，讨论方程aex=x2根的个数．

Oneofhisclassmatesbrokethewindow．Thewindow______oneofhisclassmates．

A、Delayedtreatments.B、Thequakesthemselves.C、Lackoffoodandwater.D、Collapseofbuildings.D原文讲述地震的重大损失主要是由于房屋的倒塌和其他一些因素，