题7 题目 Q:给定有 个元素的一维数组,建立一个有序单链表的最低时间复杂度是 ( ). A. B. C. D. 分析 A:用头插法，每次插入是O1的，n个元素就插入n次，这和输入的规模是一致的 注意到这里还要求有序，有序这个操作，可以在还是数组的时候做，也可以在已经是链表的时候做 解 D 若先建立链表, 然后依次插入建立有序表, 则每插入一个元素就需遍历链表寻找插入位置, 即直接插入排序,时间复杂度为 。 若先将数组排好序,然后建立链表,建立链表的时间复杂度为 ，数组排序的最好时间复杂度为 ，总时间复杂度为 。故选 D。