题目

创建一个包括n个结点的有序单链表的时间复杂度是( )。A. O(1)B. O(n)C. O(n2)D. O(nlog2n)

创建一个包括n个结点的有序单链表的时间复杂度是( )。

A. O(1)

B. O(n)

C. O(n2)

D. O(nlog2n)

题目解答

答案

C. O(n2)

解析

考查要点：本题主要考查有序单链表的构建时间复杂度，需要理解插入操作的效率与链表长度的关系。

解题核心思路：
在有序单链表中插入新节点时，每次插入都需要遍历链表以找到正确的位置。若链表初始为空，插入第k个节点时，平均需要遍历k次，总时间复杂度为所有插入操作的累加。

破题关键点：

  • 单链表的插入操作：每次插入需要线性时间（O(n)），总时间复杂度为O(n²)。
  • 区分有序与无序链表：若数据本身有序，时间复杂度可优化为O(n)，但题目未明确说明，需按最坏情况分析。

插入操作的时间分析

  1. 插入第1个节点：链表为空，直接插入，时间复杂度为O(1)。
  2. 插入第2个节点：需比较1次，时间复杂度为O(2)。
  3. 插入第k个节点：链表已有k−1个节点，需遍历最多k−1次，时间复杂度为O(k)。
  4. 总时间复杂度：
    $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2} = O(n^2).$

选项分析

  • A. O(1)：错误，插入操作与链表长度相关。
  • B. O(n)：错误，仅适用于数据已有序的情况（题目未说明）。
  • C. O(n²)：正确，每次插入平均需遍历链表长度。
  • D. O(n log n)：错误，常见于更高效的数据结构（如平衡二叉树）。