algorithm - 用 n 个元素初始化一个有序链表的复杂度是多少？

Question

假设我有n想要创建排序链表的元素。添加第一个元素只是O(1)因为列表最初是空的。然后要添加第二个元素，我必须与第一个元素进行比较，但它应该仍然是恒定的。然而，随着更多元素的添加，我对如何分析这一点感到困惑。最终，添加元素的最坏情况将达到n，因为我们将不得不遍历链表上的所有值。并且会有n插入。那么它最终会是 O(1+2+3+...+n) = O(n)吗？

标签： algorithmdata-structureslinked-listtime-complexity

Answer 1

最坏的情况下：

对于算法来说，最坏的情况是对数组进行排序。因此，对于每个元素（假设在第i个索引处），您必须比较i-1元素。

因此，时间复杂度 = O (1 + 2 + 3 ... + n-1) ~ O(n^2)。