2. 考研
  3. 线性表(a1，a2，a3，…，an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。 分别给出算法各部分的时间复杂度。

线性表(a1，a2，a3，…，an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。 分别给出算法各部分的时间复杂度。

admin2016-03-29  54
问题 线性表(a1，a2，a3，…，an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。
分别给出算法各部分的时间复杂度。
选项
答案在利用折半查找的方法查找x的过程中时间复杂度为O(nlog2n)；交换元素位置时的时间复杂度为O(1)；当查找不成功时，插入元素时的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/O2Ri777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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