如果我们有一个包含N个元素的排序数组，并且我们希望执行N个插入操作，那么最佳方法在最坏情况下的时间复杂度应该是多少？
我认为它应该是O(N log(2N))，因为我们可以直接在排序数组的末尾插入N个元素。在所有的插入之后，我们将有2N个元素，并且我们可以对整个2N阵列执行稳定的排序算法，该算法将采用O(2N-log(2N))~O(N-log(2N
因此，总共=N次插入+排序=O(N+2N个log(2N))=O(N个log(2N))
但在我看到的任何相关概念中，它都被赋予O(N^2)，因为它们通过在排序的数组之间为每次插入留出空间来保持数组在每次插入后的排序！
我的做法错了吗？我们是否必须在每次插入后对已排序的数组进行排序？如果是，那么这条"在每次操作后保持数据结构不变，而不是在一系列相同的操作后保持完整"规则对所有数据结构有效吗？！
取决于您需要什么。
如果您需要在每次插入后进行一些操作，那么O(n^2)是标准的(找到正确的点O(lgn)并移动元素O(n))。
如果在插入之间不需要执行任何操作，请在末尾插入所有元素并在O(nlgn)中排序，以便整个操作占用O(nlgn)(假设在末尾插入需要O(1)时间)。
顺便说一句，它将是O(nlg(n))，因为O(nlg(2n)) = O(nlgn + nlg(2)) = O(nlgn + n) = O(nlgn)