问删除N个步骤的时间复杂度是怎样的？

EN

假设您有一个大小为N的数组，要删除的元素位于M与M < N的位置，然后需要M步骤来查找元素，然后需要移动N-M元素，因此需要O(M + (N-M)) = O(N)

该问题假定要删除的节点是已知的，指向该节点的指针是可用的。

为了删除一个节点并将前一个和下一个节点连接在一起，您需要知道它们的指针。在双链接列表中，两个指针都在要删除的节点中可用。在这种情况下，时间复杂度是恒定的，即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)。

我认为这给了我一个关于这个话题的看法。

允许您从大小为n的数组中删除m。它取决于数组是否排序。在最坏的情况下接受一切。如果数组被排序，在数组中搜索m的最坏情况的时间复杂度是log(n)，让我们在第一个索引(0)处找到数字m，那么您需要将剩下的数组从索引1移到n-1。如果数组中搜索m的最坏情况时间复杂度为O(n)，则移位的时间复杂度为O(n)约和O(log(n))+ O(n) = O(N)。需要向左移动，则需要O(n)+ O(n) = O(N)