【学习笔记】一类比较问题

本文介绍3类比较问题

1、逆序对

问题：一列数7 3 2 1 6 8 4 5，每次操作可以任选两个相邻的数交换，问最少几次操作使得数列升序？

答案等于数列逆序对数

定义逆序对：一列数{a}中对于$i<j,a_i>a_j$，称$(a_i,a_j)$为一个逆序对

简要证明：
假如我现在是一个人工智能，我的目标使得操作数最小。
每次操作肯定是做收益最高的。
每次操作我都可以令数列的逆序对数-1

因为一列数不是有序的，必定存在相邻的两个数$a_i>a_{i+1}$
然后我交换他们
整个数列是$a_1,a_2,...,a_i,a_{i+1},...,a_{n-1},a_n$
交换之后$a_i,a_{i+1}$之外的逆序对不会受到影响，只会使得$a_i,a_{i+1}$这一对逆序对消失，所以一次操作使得数列逆序对数-1

然后最终升序的数列逆序对数为0，所以答案等于逆序对数

拓展：
若一列数有重复的数，结论是否成立？成立。

2、环

问题：一列数7 3 2 1 6 8 4 5，每次操作可以任选两个数交换，问最少几次操作使得数列升序？

前提：数互不相同。
对于每一个数，它在最终数列里位置一定是确定的。
对于最终数列的每一个位置，他最终只能放一个确定的数。
7 3 2 1 6 8 4 5
1 2 3 4 5 6 7 8
对于每个数往他的目标位置连一条有向边表示最终要到那里去。

发现数列里的数会构成至少一个环，每个数都会在某一个环里
我们交换两个数，一定会交换两个在同一个环里的数
对于一个环，环里有$x(x>=1)$个数，一定是用$x-1$次操作使得这个环变有序

所以结论就是，这列数如果能构成$k(k>=1)$个环，答案是$n-k$

3、决策树

重头戏。

对于一个有5个未知大小的数的数列，最少需要几次比较才能保证数列有序？

先算3个数的数列
第一步，可以$a<b$
第二步，若$b<c$，完成；若$c<b$，则还要第三步比较$a,c$的大小
答案为3

4个数的数列
先用3步确定3个数的大小关系$a<b<c$
令$d$与$b$比较，假设$d<b$，再把$d$与$a$比较，共用5步

上述也证明了一个引理：2次比较可以将一个数插入到有3个数的有序数列中

回到原问题。
设a,b,c,d,e
先用两次$a<b,c<d,e$
比较$b,d。设b<d$，那么$a<b<d,c<d$
再用2次可以将$e$插到$a<b<d$中
目前共用5次，知道了$a,b,d,e$之间的关系，且$c<d$
假设$a<b<e<d，c<d$这是最劣的情况，再用2次比较可以把$c$放到$a<b<e$当中去

共用7次，解决问题。

推广：决策树。
定义：决策树，每个决策可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形像一棵树，称决策树。

对于我们这个问题，当前的数之间的大小关系是一个状态，一个比较比如会出现$a<b或a>b$，引申出2个不同的新状态
所以进行$k$次操作，会有$2^k$中状态之中确定一种
5个数的大小关系有$5!=120$中可能，对应$2^7=128>120,2^6=64<120$
6次比较无法确定一个5个数的数列的顺序，7次就可以。

推广到$n$个数的数列。
至少比较多少次是的数列有序？
根据决策树，至少比较$\lfloor lo{g}_2^{n!}\rfloor$次
然而可以发现决策树并不完全正确，一次比较并不一定有效，延伸出来的两个状态并不一定不同
但是我们可以通过决策树确定比较次数的下界为$\lfloor lo{g}_2^{n!}\rfloor$约等于$\lfloor nlo{g}_2^n\rfloor -n$
这是一个未被证明，也未被证伪的结论，参考于Donald E. Knuth先生的The Art of Computer Programming

但是从算法角度上来说，我们可以得知，对一列$n$个数的数列进行基于比较的排序，时间复杂度为$O(nlo{g}_2^n)$