Question

填空题1：对于一个长读为n的顺序存储的线性表，在表尾插入元素的时间复杂度为（ ）。

Answer 1

对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为0(n)，在表尾插入元素的时间复杂度为0(1)。

顺序存储的线性表，是用数组实现的。在表尾插入元素，只要直接在表尾增加一个元素，并修改表的元素个数（加1）。所以其复杂度为0(1)。

扩展资料：

时间复杂度的计算方法：

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) 的同数量级

（它的同数量级有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))

Answer 2

O(1)
在表尾插入元素，不需要涉及到其他元素的移动，只需要将待插入元素插入在线性表末尾即可，故时间复杂度是常量阶。

Answer 3

顺序存储的线性表，是用数组实现的。在表尾插入元素，只要直接在表尾增加一个元素，并修改表的元素个数（加1）。所以，其时间复杂度为O（1）。

Answer 4

对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_0(n)__，在表尾插入元素的时间复杂度为__0(1)__。

Answer 5

时间复杂度表示是O(n)