这题为什么是o（n）？找到插入的位置后不是还得移动元素吗？怎么不是o（n^2）？
- 在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一
- 在数组指定位置插入元素的两种方法哪个时间复杂度
- 请问顺序表中插入结点时如平均移动次数为n/2，为什么说它的时间复杂程度O(n)而不是O(n/2)?
- O(n)是什么
在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一
元素的移动次数为n-i+1，选A。
举例说明：如1 2 3。在第2个位置插入一个a，则变成：1 a 2 3，2和3分别后移一位，所以总共移动3+1-2=2次。
顺序表的存储特点只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L是元素占用存储单元的长度。
扩展资料：
顺序表的结构定义：
#define maxlen 50 //定义顺序表中元素个数最多有几个
typedef struct
{
elementtype data[maxlen]; //elementtype是元素的类型 依具体情况而定
int listlen; //便于时刻了解顺序表里元素的个数
}seqlist; //顺序表的名称 不妨为seqlist
声明顺序表类型变量：
seqlist L,L1;
如顺序表的每个结点占用len个内存单元，用location (ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系:location (ki+1) = location (ki) +len
location (ki) = location(k1) + (i-1)len
存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。
在数组指定位置插入元素的两种方法哪个时间复杂度
查找插入位置如果用遍历查找的是O(n)，用二分查找是O(log2n)。
但是数组的插入操作需要将插入位置后的元素全部后移一位，这需要O(n)。
所以总的时间复杂度是O(n)。（O(n)+O(n)=O(n)，O(log2n)+O(n)=O(n)）
请问顺序表中插入结点时如平均移动次数为n/2，为什么说它的时间复杂程度O(n)而不是O(n/2)?
时间复杂度指算法执行过程中所需要的基本运算次数。你的只是一个大体评估的方式。
---------------------------------------------------------------------
大O表示法是根据数据梯度产生的变化而评估。
-----------------------------------------------------------------------
大O表示法表示时间复杂度的时候取一个下限即可，不用那么精确。
-----------------------------------------------------------------------------------------
可能你认为o(N)和o(N/2)有区别，但实际上这两者对于大O表示法表示的时间复杂度来说没区别，大O表示法表示的时间复杂度关注的是数据量的增长导致的时间增长情况，o(N)和o(N/2)在数据量增加一倍的时候，时间开销都是增加一倍（线性增长）。所以都认为是O(N)
-------------------------------------------------------------------------------------------
但是程序优化的时候就要精确评估了！能提高多少就提高多少。
O(n)是什么
O(n)不是算法，它是一个函数，是一个表征算法时间复杂度的一个函数。
计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。
使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。
扩展资料：
算法复杂度分为时间复杂度和空间复杂度。
其作用： 时间复杂度是指执行算法所需要的计算工作量；
而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度）。
计算方法：
1、一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得T(n)/f(n)的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
分析：随着模块n的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。
2、在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级，找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))。
则该算法的时间复杂度：T(n) = O(n^3) 注：n^3即是n的3次方。
3、在pascal中比较容易理解，容易计算的方法是：看看有几重for循环，只有一重则时间复杂度为O(n)，二重则为O(n^2)，依此类推，如果有二分则为O(logn)，二分例如快速幂、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)。
参考资料：搜狗百科-时间复杂度