设一个有序的单链表中有 n 个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为( )。
(A) O(log2n)
(B) O(1)
(C) O(n^2)
(D) O(n)
算平均情况,思路如下:(算遍历的平均次数,和数组插入的移动平均次数有些类似)
假设这个有序单链表拥有头节点,且递增。
那么插入一个新结点仍要使得它有序递增的话,可以从第一个结点遍历单链表,直到找到一个大于它的结点,在那个结点前插入就行(若找不到就在成为尾巴)。
n个顶点n种情况:
1、新结点最小,比较第一个结点,小于,头插即可,遍历即比较次数--->1。
2、新结点倒数第二小,比较第一个结点,大于,第二个结点,小于,插入第一个结点后面,遍历次数--->2。
依次类推......
n个结点的遍历总数为Σ(i=1...n) i = 1 + 2 + ... + n = (n / 2) * (1 + n)
平均下来再除以一个n,得到(1 + n) / 2,即时间复杂度为O(n)。
(希望对你有所帮助~~)
应该算最坏情况吧?
D
用户登录可进行刷题及查看答案
登录后提交答案