删除N个步骤的时间复杂度是怎样的？
删除N个步骤的时间复杂度是怎样的？
提问于 2021-07-26 13:57:19
我开始自学数据结构和算法，目前正在学习数组的时间复杂性。
从我正在学习的书中，它指出搜索数组需要N个步骤，因为最坏的情况是，您必须搜索每个单元格以获取数据元素。
那么为什么从数组中删除也有N个步骤呢？
据我所知，计算机为数组分配内存，并通过内存地址注意数组的开头。对于删除，您是否仍然需要搜索数组的每个索引以查找要删除的数据元素，删除该数据元素，然后移动其余的数据元素？
也许我还太早进入这一章，但对于删除本身如何只需要一步，我感到很困惑。
Stack Overflow用户
发布于 2021-07-26 14:08:44
该问题假定要删除的节点是已知的，指向该节点的指针是可用的。
为了删除一个节点并将前一个和下一个节点连接在一起，您需要知道它们的指针。在双链接列表中，两个指针都在要删除的节点中可用。在这种情况下，时间复杂度是恒定的，即O(1)。
而在单链列表中，指向前一个节点的指针是未知的，只能通过从头遍历列表直到到达具有下一个要删除节点的节点指针的节点才能找到。这种情况下的时间复杂度是O(n)。实际上，单链表中的删除也可以在O(1)中实现。
给定具有以下状态的单链列表：
SinglyLinkedList:
Node 1 -> Node 2
Node 2 -> Node 3
Node 3 -> Node 4
Node 4 -> None
Head = Node 1在已知位置插入和删除的是O(1)。但是，找到这个位置是O(n)，除非它是列表的头或尾。
当我们谈到插入和删除的复杂性时，我们通常假设我们已经知道这将发生在哪里。
在只有值知道要删除的节点的情况下，必须搜索列表，并且在单链表和双链表中，时间复杂度都变成O(n)。
我认为这给了我一个关于这个话题的看法。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/68531217
复制相关文章
相似问题
腾讯云开发者
