问答题

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

【参考答案】

正确答案：在利用折半查找的方法查找x的过程中时间复杂度为O(nlog ₂ n)；交换元素位置时的时间复杂度为O(1)；当查找不成功时，插入元素时的时间复杂度为O(n)。

<上一题目录下一题>

热门试题

问答题根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

问答题给出算法的基本设计思想。