algorithm - 链表移除操作时间复杂度 O(n) vs O(1)

当我回顾数据结构和算法的大 O 表示法时，当不同来源将 O(n) 时间复杂度用于从链表中删除节点与 O(1) 相比时，我感到困惑。例如，big O cheat sheet在删除节点时放置 O(1)，因为我认为删除节点将是 O(n)，因为您必须先找到该节点然后将其删除。

那么我的问题是，O(1)的时间复杂度是不是只假设了删除操作本身，而没有考虑到必须先找到节点呢？让我们假设要删除的节点位于列表中的任何位置，而不仅仅是列表的前端或末尾。

我已经查看了以下问题，但它们没有解决我的问题:

最佳答案

你的问题的答案是:是的。

通常，当声明在链表中插入或删除的时间复杂度为 O(1) 时，假定指向相关节点的指针是已知的。然而，这并非完全没有用。考虑您要遍历列表并删除与特定描述匹配的元素的情况。使用链表，这可以在 O(n) 时间和 O(1) 额外空间内完成。对于数组，这通常需要 O(n^2) 时间或 O(n) 额外空间。

关于algorithm - 链表移除操作时间复杂度 O(n) vs O(1)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54173593/

相关文章：

c++ - 如何使用Trie数据结构查找所有可能子串的LCP总和？