在一个具有n个节点的有序单链表中插入一个新节点并使其仍然有序的时间复杂度为 【 】

admin2017-10-26  34

问题 在一个具有n个节点的有序单链表中插入一个新节点并使其仍然有序的时间复杂度为    【    】

选项 A、O(1)
B、O(n)
C、O(n2)
D、O(log3n)

答案B

解析 在有序单链表中插入一个节点并使其保持有序,花费时间最多的是查找插入位置。对具有n个节点的单链表来说,查找位置的平均比较次数是(n+1)/2,故时间复杂度为O(n)。
转载请注明原文地址:https://kaotiyun.com/show/j9kx777K
0

最新回复(0)