楼上上题解看不懂

ls题解看不懂

分析
考虑由两两交换完成的排序过程。可以想见，对每组输入数据，存在一个划分，使该划分中每个含m个元素的子集在基于原序列的顺序的两两对换的意义下生成一个m阶置换群。取一个划分X，使得其中的每个子集S在置换群意义上是极小的，即，对任意m < card(S)，不存在S的含m个元素的子集，使其元素可以以同样方式生成一个置换群。
考虑任意S的排序过程。
定理1 对于单一的置换群G对应的子集(card(S) > 1)，将其通过两两对换排序的最小“排序代价”为：
Sum + (N-2) X LocalMin
其中，sum为G对应子集S的所有元素的和，N = card(S)，LocalMin为S的最小元素。
当然，当S中只有一个元素时，其排序代价为0.
证明：
1. 存在一种排序方案，其代价为上述公式的值。
考虑由两两对换形成的循环，每次交换最小元及其相邻元即可。
2. 最优性。
任意排序方案，其最低兑换次数为N-1，且这N-1次对换须移动S的所有元素。则这一方案的最小代价即为上述公式的值。
当数据被分为多个子集时，排序可能引入外部元素。
定理2 当引入外部元素时，G(card(S) > 1)的最小“排序代价”为：
Sum’ + (N-2) X GlobalMin + 2*(GlobalMin + LocalMin)
其中，Sum’ = Sum – LocalMin + GlobalMin;
GlobalMin 为输入数据中的最小元素。
证明：
1. 存在一种引入外部元素的排序方案，其代价为上述公式的值。
将外部最小元GlobalMin 与内部最小元LocalMin对换，再将其与剩余内部元素组成的数据按照定理1的方式排序，最后再次将GlobalMin与LocalMin对换即得。
2. 最优性。
任意引入外部元素的排序方案，与定理1类似地，其最低代价为上述公式的值。
由上述公式，如果被排序的子集包含全局最小元，则任意引入外部元素的排序方案都将具有大于内部最优方案的排序代价。是以定理1与定理2给出公式的最小值为待排序子集的最小排序代价。在上述划分方式下，原问题的解具有局部最优性，是以对每个子集的最小排序代价做和即得原问题的最优解。
From
<风和凌释>http://blog.sina.com.cn/arkpku