因此，如果您使用快速排序对数组进行排序，则可以使用QuickSort在O（nlogn）中进行操作，然后一旦对其进行排序，就可以将新元素插入O（logn）带有二进制搜索风格的算法。
我的问题是，是否有一种方法可以证明，如果您可以在O（logn）时间中插入一个排序的数组，那么这意味着分类算法至少必须是O（nlogn）？
换句话说，两种算法的运行时间之间是否存在关系？
no：可以使用bubblesort（o（n²））对数组进行排序。之后，仍然可以使用相同的算法在O（log（n））时间插入。
好吧，维持顺序的插入为o（log n）的事实意味着可以在O（n log n）中执行排序操作，而仅通过将每个元素依次插入到大批。但是，这可能与您真正要求的相反。它证明存在O（n log n）排序，但并没有反驳更快的类型的可能性。
首先，某些需要特殊条件的分类算法具有潜在的时间复杂性。例如，计算具有O（n K）复杂性（k是数组中的最高数字）或radix排序的计数排序，其复杂性（n*k）的复杂性（其中k是数组中数字的最大数字元素）。
O（nlogn）的界限适用于比较算法。
第二，回答问题，不（可悲）。就像Davmac所说，插入和分类之间的关系是相反的。
比较下界的原因是您至少需要Nlogn比较才能找到正确的顺序。有关更多详细信息，请参见比较分类算法上的Wiki页面。请注意，教授与插入无关（教授实际上没有任何插入）。