对于顺序存储结构，查找插入位置 i 的时间复杂度为 O(1)，因为可以直接通过下标访问第 i 个位置。
插入元素后，如果在数组中间插入，那么需要将从插入位置 i 开始的后续元素依次向后移动一个位置，以腾出空间给新元素。这部分的时间复杂度为 O(n-i)。
因此，总的时间复杂度为 O(1) + O(n-i) = O(n-i)。
注意，如果插入位置 i 靠近表尾，即 i 接近 n，则时间复杂度接近 O(1)。但如果插入位置 i 靠近表头，即 i 接近 1，则时间复杂度接近 O(n)。在最坏情况下，当插入位置 i=1 时，时间复杂度为 O(n)。在平均情况下，可以视为 O(n/2)，即 O(n)。因此，我们可以将插入操作的时间复杂度近似表示为 O(n)。
对于顺序存储结构，查找插入位置 i 的时间复杂度为 O(1)，因为可以直接通过下标访问第 i 个位置。
插入元素后，如果在数组中间插入，那么需要将从插入位置 i 开始的后续元素依次向后移动一个位置，以腾出空间给新元素。这部分的时间复杂度为 O(n-i)。
因此，总的时间复杂度为 O(1) + O(n-i) = O(n-i)。
注意，如果插入位置 i 靠近表尾，即 i 接近 n，则时间复杂度接近 O(1)。但如果插入位置 i 靠近表头，即 i 接近 1，则时间复杂度接近 O(n)。在最坏情况下，当插入位置 i=1 时，时间复杂度为 O(n)。在平均情况下，可以视为 O(n/2)，即 O(n)。因此，我们可以将插入操作的时间复杂度近似表示为 O(n)。
zhangziyun
回复
我超白好嘛：
我觉得这里n-(i-1)不做一些说明可能理解有一点误导。前面刚说完元素位置a[i-1]，后面紧接着说要将n-(i-1)个元素向后挪动，给人一种是用长度-从0开始计数的某元素的位置（特别强调是从0开始计数），虽然结果是对的，但是逻辑上有问题，很难理解。
我觉得最简单的理解n-(i-1)就是：既然在位置 i 处插入一个元素，那么就要将位置 i 处的元素以及后面的每一个元素向后移动一位，n-i是 i 后面的元素个数，算上 i 还要加1，所以是n-i+1，即为 n-(i-1)
注：这道题是让求时间复杂度，这种少 1，多 1的细节并不影响你做对这道题目，这样分析我只是觉得严谨一些。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案