algorithm - 对堆栈中的数字序列进行排序所需的最少操作数

Question

我们在堆栈中有 N 个数字，我们想用最少的操作数对它们进行排序。唯一可用的操作是反转堆栈顶部的最后 K 个数字(K 可以在 2 和 N 之间)。

例如排序序列“2 3 4 5 1”，我们需要2个步骤:

2 3 4 5 1 ---> 1 5 4 3 2 ---> 1 2 3 4 5

是否有任何多项式算法可以找到所需的最少步数？

Answer 1

我想您是在谈论著名的 Pancake 排序算法。

Quoting from wikipedia : "The maximum number of flips required to sort 
any stack of n pancakes has been shown to lie between (15/14)n and (18/11)n,
but the exact value is not known. The simplest pancake sorting algorithm requires
at most 2n−3 flips. 

In this algorithm, a variation of selection sort, we bring the largest pancake
not yet sorted to the top with one flip, and then take it down to its final 
position with  one more, then repeat this for the remaining pancakes.

Note that we do not count the time needed to find the largest pancake, only the
number of flips; if we wished to create a real machine to execute this algorithm
in linear time, it would have to both perform prefix reversal (flips) and be
able to find the maximum of a range of consecutive numbers in constant time"