我目前正在借助Tim Roughgarden的斯坦福名课学习算法和数据结构。在视频13-1中，他在讲解平衡二进制搜索树时，将其与排序数组进行了比较，并提到我们不在排序数组上进行删除操作，因为它太慢了（我相信他是指 "与其他操作相比，我们可以在恒定的[Select, MinMax, PredSucc]、O(log n)[Search, Rank]和O(n)[Outputprint]时间内运行，速度较慢").
我无法停止对这句话的思考。也就是我无法绕过下面的问题。
假设我们得到了一个顺序统计或我们想从一个排序(升序)数组中删除的项目的值。
我们肯定可以使用Select或Search分别在恒定或O(n)时间内找到它在数组中的位置。
然后，我们可以删除这个项目，并在被删除的项目右边迭代，将它们的指数递增1，这将需要O(n)时间。[这是我（可能是不成功的）试图描述 "将它们每个都向左移动1个位置 "的操作]
在最坏的情况下，整个操作将需要线性时间--O(n)。
关键问题 - 我是不是想错了？如果不是，为什么会被认为速度慢、不可取？
你是正确的：从数组中删除是很慢的，因为你必须将它之后的所有元素向左移动一个位置，这样才能覆盖你创造的洞。
无论 O(n) 被认为是慢的，这取决于情况。从一个数组中删除很可能是一个更大、更复杂的算法的一部分，例如在一个循环中。这样就会增加一个 n 的复杂性，这通常是不好的。使用树状结构只会增加一个系数 log n和 O(n log n) 是 很多 胜过 O(n^2) (渐进地)。
该语句是相对于特定的数据结构而言的，该结构被用来保存排序值。一个排序的数组。 选择这种特定的数据结构是为了简单、高效存储和快速搜索，但从数据结构中添加和删除元素的速度很慢。
也可以选择其他持有排序值的数据结构。 例如，二叉树，或平衡二叉树，或三叉树。 每种结构在操作性能和存储效率方面都有不同的特点，会根据预期的用途来选择。
一个排序数组对于添加和删除来说是很慢的，因为平均来说，这些操作需要移动数组的一半来为一个新元素腾出空间（或者，分别填入一个清空的单元格）。
然而，在许多架构上，数据结构的简单性和移位的速度意味着该数据结构对于 "小 "数据集是没有问题的。