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

admin2017-10-26 40

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

选项 A、O(1)
B、O(n)
C、O(n²)
D、O(log₃n)

答案B

解析在有序单链表中插入一个节点并使其保持有序，花费时间最多的是查找插入位置。对具有n个节点的单链表来说，查找位置的平均比较次数是(n+1)／2，故时间复杂度为O(n)。

转载请注明原文地址:https://jikaoti.com/ti/WHdaFFFM

计算机软件基础

相关试题推荐

随机试题

最新回复(0)