Question

一道关于数据结构时间复杂度的题

1、对于一个长度为n的单链接存储的线性表，在表头插入元素的时间复杂度为__在表尾插入元素的时间复杂度为__

2、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为__在表尾插入元素的时间复杂度为__

我知道答案是多少，但是不知道为什么，希望能给予详细的回答，谢谢。

Answer 1

1. 表头插入时间复杂度O(1），因为不需用移动元素，常数时间完成操作；表尾插入复杂度O(n)，因为每次操作都需用把指针先移动到表尾，需用n次移动。

2. 顺序存储的线性表表头插入复杂度O(n)，因为每次操作前，都需用把n个元素从尾部开始向后移动一位，需用n次移动；在表尾插入元素的时间复杂度为O(1)，因为元素可以直接完成插入，不用向后移动元素，并且元素定位（寻址）时间不用考虑。