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

admin2020-02-26  30

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

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

答案A

解析 寻找最大项,无论如何都要查看所有的数据,与数据原始排列顺序没有多大关系,无所谓最坏情况和最好情况,或者说平均情况与最坏情况下的时间复杂度是相同的。而查找无论是对分查找还是顺序查找,都与要找的数据和原始的数据排列情况有关,最好情况是第1次查看的一个数据恰好是要找的数据,只需要比较1次;如果没有找到再查看下一个数据,直到找到为止,最坏情况下是最后一次查看的数据才是要找的,顺序查找和对分查找在最坏情况下比较次数分别是n和log2n,平均情况则是“l~最坏情况”的平均,因而是不同的。
转载请注明原文地址:https://kaotiyun.com/show/JXYp777K
0

相关试题推荐
随机试题
最新回复(0)