单选题
给定有n个元素的一维数组，建立一个有序单链表的时间复杂度是______。
A.O(1)
B.O(n)
C.O(n
2
)
D.O(nlog
2
n)
A
B
C
D
【正确答案】
C
【答案解析】
[解析] 每当插入一个元素时，就必须对整个链表进行遍历找到插入位置。如果需要插入的元素有n个，则每一次遍历操作的时间复杂度为O(n)。因此建立有序单链表的时间复杂度为O(n
2
)，即链表插入排序。
提交答案
关闭