UC知道关于单链表时间复杂度问题
来源：百度知道 编辑：UC知道 时间：2024/05/28 10:22:23
我看说是单链表对于插入，删除的时候，
时间复杂度是常数阶，而顺序存储是O(n)
但是，顺序的查找元素是常数阶，而单链表这块是
O(n)，但是，我觉得，如果插入的话，首先就是要插找啊，
难道查找不用时间的啊？所以，我认为单链表的插入和删除
也应该是O(n)的啊，不知道我哪块理解错了，请高手指点。
谢谢。
啊？这样啊，
就是说不算上查找的啊？
但是一般不是都给的头指针吗？还是要查的啊。
时间复杂度是常数阶，而顺序存储是O(n)
但是，顺序的查找元素是常数阶，而单链表这块是
O(n)，但是，我觉得，如果插入的话，首先就是要插找啊，
难道查找不用时间的啊？所以，我认为单链表的插入和删除
也应该是O(n)的啊，不知道我哪块理解错了，请高手指点。
谢谢。
啊？这样啊，
就是说不算上查找的啊？
但是一般不是都给的头指针吗？还是要查的啊。
呵呵， 如果是要查找的话，那当然是o(n)了
但在实际使用时，我们一般是已知一个结点，例如结点p,要在它的后面插入一个结点q， 这时就是常数阶的复杂度了
q->next = p->next;
p->next = q;