升序排序数组传入Reversort算法的时间复杂度是多少？

先给明确答案：仍然是O(n²)，不会降到O(n)

具体分析 #

先看原算法的核心步骤：

Reversort(L): 
for i := 1 to length(L) - 1
    j := position with the minimum value in L between i and length(L), inclusive
    Reverse(L[i..j])

当输入是升序数组时：

• 每一轮循环里，[i, n]区间的最小值就是L[i]，所以j必然等于i，这时候反转L[i..j]其实就是反转单个元素，这个操作的时间是O(1)，几乎没开销。
• 但关键开销在查找最小值位置的步骤：原算法要求必须遍历[i, n]的所有元素来确定最小值的位置，哪怕数组已经有序，这个遍历过程也不能跳过。

总时间计算 #

第一轮i=1，要遍历n个元素；i=2，遍历n-1个；……直到i=n-1，遍历2个元素。总遍历次数是：
n + (n-1) + ... + 2 = (n² + n - 2)/2
这个量级显然是O(n²)，而反转操作的总时间是O(n)，可以忽略。所以整个算法的时间复杂度还是O(n²)。

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