向一个有序数组中插入一个数的时间复杂度是多少

2025-04-14 15:13:07
推荐回答(1个)
回答1:

查找插入位置如果用遍历查找的是O(n),用二分查找是O(log2n)。
但是数组的插入操作需要将插入位置后的元素全部后移一位,这需要O(n)。
所以总的时间复杂度是O(n)。(O(n)+O(n)=O(n),O(log2n)+O(n)=O(n))