给定有n个元素的一维数组，建立一个有序单链表的最少时间复杂度是（ ）。

Question

A.O(1)
B.O(n)
C.O(n2)
D.O(nlog2n)

Answer 1

【答案】：D
若先建立链表，然后依次直接插入建立有序表，则每插入一个元素就需遍历链表寻找插入位置，此即链表插入排序，时间复杂度为O(n2)。若先将数组排序，然后建立链表，建立链表的时间复杂度为O(n)，而数组排序的最少时间复杂度为0(nlog2n)，故时间复杂度为O(nlog2n)。本题问最少时间复杂度，故选D。