在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（）。A.O(n)B.O(1)C.D.O(n-1)正确答案：O(n)

时间复杂度是O(n)在一个具有n个节点的单链表中删除第i个节点算法的时间复杂度是o(n)；因最坏情况是删除最后一个结点，所以要找到最一个结点的前驱，也就要访问前n-1个结点，故算法的时间复杂度为o(n)。for（i=1;...

单链表查找的时候要一直找下一个结点，若要查找的元素在最后，就相当于找了n次，所以时间复杂度为：O(n)

访问后继结点只是进行一次间接寻址的操作，时间是常量，所以是O（1）。链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息。...

p从单链表头开始到尾结束。i=1->n对于固定的p，q从p位置开始，遍历到表尾。j=i->n对于固定的q，每次r从表头开始，直到r与q不相等，即遍历到q位置结束。k=1->j-1因此最后复杂度为O(n...

因为o（n^2），对单链表而言，一些快速的排序算法，不能用，只能用直接插入等o（n^2）级的排序算法来实现排序。因为是有序单链表那么每次插入到链表尾结点，那么每次插入都要从头扫到尾，然后1+2+3+...m=O（m...

要插入到长度为m的单链表，需要找到表尾，这个过程的时间复杂度为o(m)，连接的时间复杂度为o(1)，所以总的时间复杂度为o(m)，所以答案选C。单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的...

若要插入的元素大于表中的最大元素，则需要与表中的n个元素全部比较一遍。因此，单链表中参与比较的元素个数平均为(1+2+…+n+n)/(n+1)，即该操作的时间复杂度为O(n)。

时间复杂度是O(1)访问前驱节点需要从头结点开始根据链表顺序一个一个访问。该步骤有一重循环，基本运算次数与问题规模n的增长呈线性增大关系，所以时间复杂度是O(n)。如果是双向链表p=p->prior就能访问前驱节点。

但是还是部分适用的，比如归并排序，希尔排序，和快速排序的特定实现。就算这些算法你统统不考虑，还有一种简单粗暴的方法：将链表复制到数组排序数组将数组还原成链表这三步的复杂度是O(n+nlogn+n)=O(nlogn)