求数组最小待排序窗口算法的时间与空间复杂度相关问题解答

你的判断完全正确，该解法的空间复杂度实际为O(n)，作者给出的O(n log n)结论是错误的，大概率是混淆了时间复杂度与空间复杂度的表述。

我们可以完整拆解该解法的所有空间开销：

• 核心额外开销是sorted(array)生成的排序后数组副本，需要存储和输入数组等长的n个元素，空间占用为O(n)
• left、right两个边界指针仅占用常数级空间，空间占用为O(1)
• Python内置排序使用的Timsort算法自身的运行时额外空间开销同样为O(n)，不存在对数级额外空间叠加的情况

整个算法没有其他额外空间开销，累加后的总空间复杂度为O(n)，不可能达到O(n log n)的量级。

如果追求更优的空间表现，该问题还存在不需要额外排序数组、时间复杂度O(n)、空间复杂度O(1)的优化解法：分别从左到右遍历找右边界、从右到左遍历找左边界即可，不需要存储完整的排序后数组。

内容的提问来源于stack exchange，提问作者Hayk