时间戳

首页 > 解决方案 > 链表的时间复杂度是多少？

c - 链表的时间复杂度是多少？

问题描述

假设您想在保持排序顺序的同时将n个元素插入一个空链表中。最坏情况时间是多少？

标签： cdata-structureslinked-list

解决方案

如果，通过“保持排序顺序”，您的意思是它们已经排序，这是一个O(n)操作，因为您只需将它们中的每一个都放在列表的末尾（并且您可以保留当前结尾的记录而不是搜索每次都为它）：

make new list from first value, keeping pointer to last, O(1)
for curr in second and subsequent values, O(n):
    add to list using last, update last, O(1)

如果您的意思是它们没有排序但它们应该是，那将是，因为每个新值都会导致搜索后跟插入：O(n2)nO(n)O(1)

for curr in values, O(n):
    find insertion point, O(n)
    insert at that point, O(1)

推荐阅读