删除 N 个步骤的时间复杂度又名 O(n) 是多少？

Question

我开始自学数据结构和算法，目前正在学习数组的时间复杂度。

从我正在学习的书中，它指出搜索数组需要 N 个步骤，因为最坏的情况是您必须在每个单元格中搜索数据元素。

那为什么从数组中删除也是N步呢？

据我了解，计算机为数组分配内存，并通过内存地址记录数组的开头。删除的话，不是还要在那个数组的每个索引中搜索要删除的数据元素，删除那个数据元素，然后移动剩余的数据元素吗？

也许我对这一章还为时过早，但我对删除本身如何只需要 1 个步骤感到很困惑。

Answer 1

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

Answer 2

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

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

我认为这提供了对主题的看法

Answer 3

允许您从大小为 n 的数组中删除 m。它取决于数组是否排序。把一切都放在最坏的情况下。如果数组已排序，则在数组中搜索 m 的最坏情况时间复杂度为 log(n) 让我们在第一个索引（0）处找到数字 m 然后你需要将数组从索引 1 左移到 n-1。移位的时间复杂度约为 O(n) 且 O(log(n))+O(n)= O(n) 如果数组没有排序最坏情况下在数组中搜索m的时间复杂度是O(n)中的。并且需要左移，需要 O(n)+O(n)= O(n)

删除 N 个步骤的时间复杂度又名 O(n) 是多少？

How is the time complexity of deletion N steps aka O(n)?

arrays

time-complexity

data-structures