当我回顾数据结构和算法的大O表示法时,我困惑于不同的源在O(n)时间复杂度中删除一个链表中的节点而不是O(1)。例如,big O cheat sheet在删除节点时放置O(1),我认为删除节点将是O(n),因为必须先找到该节点,然后再将其删除。
所以我的问题是,O(1)的时间复杂度是否假定删除本身的操作而不考虑节点必须首先找到?让我们假设要删除的节点在列表中的任何位置,而不仅仅是在列表的前面或末尾。
我回顾了以下问题,但它们没有回答我的问题:
big O notation for removing an element from a linked list
Big-O summary for Java Collections Framework implementations
What are the time complexities of various data structures?
最佳答案
你的问题的答案是:是的。
通常,当O(1)时间复杂度被表示为在链表中插入或删除时,假定指向所讨论的节点的指针已经知道。不过,这并非完全无用考虑这样一种情况:您希望遍历一个列表并删除与特定描述匹配的元素使用链表,这可以在o(n)时间内完成,而o(1)额外的空间。对于数组,这通常需要O(n^2)时间或O(n)额外空间。