问题
问答题
线性表(a1,a2,a3,…,an)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素,请设计一个时间复杂度最低的算法。找到x后,将其与后继元素位置相交换。如果线性表中没有x,将其插入表中并使表中元素仍递增有序。请回答下列问题:
总结所用算法的时间和空间复杂度。
答案
参考答案:折半的时间复杂度为O(logn),如果不存在x的情况下,在线性表中插入元素的时候,时间复杂度取决于x插入的位置,最坏情况下为O(n)。算法实现过程中使用的辅助空间为常量,空间复杂度为O(1)。