关于仅翻转前缀的数组排序算法时间复杂度的疑问

首先要明确：时间复杂度的计算不能只看操作的次数，还要考虑每次操作的时间成本——你用到的「翻转前缀」操作并不是O(1)的常数时间，而是和前缀的长度成正比的O(k)时间（k是当前翻转的前缀元素个数）。

算法过程的时间拆解 #

你的算法逻辑本质和**煎饼排序（Pancake Sorting）**一致，核心是通过两次翻转将未排序部分的最大元素移到正确位置：

• 第一步：翻转前缀，把未排序部分的最大元素移到数组头部（时间O(k)，k是该元素所在位置的索引+1）
• 第二步：翻转整个未排序部分的前缀，把这个最大元素移到未排序部分的末尾（时间O(m)，m是当前未排序部分的长度）

对于长度为n的数组，每个元素最多需要两次翻转操作，而每次翻转的时间开销从n递减到1，总时间是累加的：
n + (n-1) + (n-2) + ... + 1 = n(n+1)/2，这显然是O(n²)的时间复杂度。

结合你的示例验证 #

以数组3,4,1,2（n=4）为例，各步骤的时间开销：

1. 翻转前2个元素得到4,3,1,2：时间O(2)
2. 翻转前4个元素得到2,1,3,4：时间O(4)
3. 翻转前3个元素得到3,1,2,4：时间O(3)
4. 翻转前2个元素得到2,1,3,4：时间O(2)
5. 翻转前2个元素得到1,2,3,4：时间O(2)

总时间开销为2+4+3+2+2=13，对应n=4时n²=16，是同一量级的数值。

总结 #

你的错误在于忽略了「翻转前缀」操作本身的时间成本，只统计了操作次数。这类基于前缀翻转的排序算法，时间复杂度都是O(n²)，无法达到O(n)——因为O(n)排序需要每个元素的处理是常数时间，而翻转操作做不到这一点。

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