题目
创建一个包括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)
解析
创建一个包括n个结点的有序单链表的时间复杂度主要取决于插入操作的复杂度。在最坏的情况下,每次插入一个新结点时,都需要遍历整个链表来找到合适的位置。因此,对于n个结点,总共需要进行n次插入操作,每次插入操作的平均时间复杂度为O(n),所以总的时间复杂度为O(n^2)。