Question

建立一个长度为n的单链表的时间复杂度为？

Answer 1

引用草根英雄1的回答：
O(n^2)

尾插入的话，并不用每次都遍历，只要把当前的结点赋给一个temp指针就好
所以答案应该是O(n)

Answer 2

也可以是O(1)
看是在表尾加，还是在表头加（让新元素成为表头）

Answer 3

应该是O(n)

Answer 4

可是课本上的头插法的算法是一个for循环，不应该是n吗？

Answer 5

O(n^2)

追问

为什么是这外答案，而不是其他的，如O(n)或O(1)

追答

简单啊，建立链表的方法是什么，我假设是尾插入，那么每添加一个节点需要进行的操作为，遍历到末尾，然后在添加，那么第一次添加，直接在head后添加，第二次，遍历第一个节点，插入到第一个节点的后面，如此类推，遍历的时间复杂度就为1+2+``````+n - 1 +n，添加节点操作的时间复杂度忽略，大致的结果就是前面那个表达式的值，把它写成n^2 - n/2(可能不对，但一定有n^2)，那么舍去低阶和常数，得O(n^2 /2)，舍去常数因子，得O(n^2)；为什么舍去，是因为随着问题规模的增大，低阶函数对结果的影响趋于0，常数因子的影响趋于0.