171 lines
5.0 KiB
Markdown
171 lines
5.0 KiB
Markdown
# 排序问题
|
||
|
||
## T1
|
||
|
||
### T1.1
|
||
|
||
对于 $\boldsymbol{\mu}$ 的任一分量 $\mu_{i}$, 我们可以知道 $\forall\mu\in\mathbb{R}$, $|\mu-\sigma_{i}^{1}|+|\mu-\sigma_{i}^{2}|+\cdots+|\mu-\sigma_{i}^{k}|>|\mu_{i}-\sigma_{i}^{1}|+|\mu_{i}-\sigma_{i}^{2}|+\cdots+|\mu_{i}-\sigma_{i}^{k}|$, 我们可以知道, $\mu_{i}$ 为 $\set{\sigma_{i}^{1},\sigma_{i}^{2},\cdots,\sigma_{i}^{k}}$ 的中位数
|
||
|
||
$$
|
||
\therefore \mu_{i} = \begin{align}\left\{\begin{aligned}
|
||
\sigma_{i}^{k/2}, k为偶数\\
|
||
\sigma_{i}^{(k+1)/2}, k为奇数
|
||
\end{aligned}\right.\end{align}
|
||
$$
|
||
|
||
我们取 $\boldsymbol{\sigma}_{i}^{\prime}$ 为 $\mu_{i}$ 在 $\set{\mu_{0},\mu_{1},\cdots,\mu_{k}}$ 中的排序，对于相同的值则随机排序，即为一种综合排序。然而，$\boldsymbol{\sigma^{\star}}$ 不能从中得出，因为可能有相同的值。
|
||
|
||
### T1.2
|
||
|
||
|
||
|
||
对于 ABC 三点，C 在线段 AB 上，$|C-A|+|C-B|=const$ 所以我们可以认为这两个点对于 $\sum\limits_{i=0}^{n}|\boldsymbol{\beta}_j-\sigma_j^i|$ 与 $\sum\limits_{i=0}^{n}|\boldsymbol{\mu}_j-\sigma_j^i|$ 的贡献是相同的，所以我们可以令
|
||
|
||
$$
|
||
\sum\limits_{i=0}^{n}|\boldsymbol{\beta}_j-\sigma_j^i|=C+x_1
|
||
$$
|
||
|
||
$$
|
||
\sum\limits_{i=0}^{n}|\boldsymbol{\mu}_j-\sigma_j^i|=C+x_2
|
||
$$
|
||
|
||
其中常数 C 是共同贡献的总值，于是
|
||
|
||
$$
|
||
\frac{\sum\limits_{i=0}^{n}|\boldsymbol{\beta}_j-\sigma_j^i|}{\sum\limits_{i=0}^{n}|\boldsymbol{\mu}_j-\sigma_j^i|}=\frac{C+x_1}{C+x_2}
|
||
$$
|
||
|
||
可知常数 C 越小，比值越大
|
||
|
||
假设 $n-1$ 个点重合，排序 $\sigma_j^i = N$ 点 $A$ 距离 $\sigma_j^i$ 距离为 $x$
|
||
|
||
|
||
|
||
$\mu_j$ 为中位数，所以 $\mu_j$ 与 N 点重合
|
||
|
||
$$
|
||
\sum\limits_{i=0}^{n}|\mu_j-\sigma_j^i|= x
|
||
$$
|
||
|
||
$\mu_j$ 为平均数， $|\mu_j - N|=\frac{x}{n}$
|
||
|
||
$$
|
||
\sum\limits_{i=0}^{n}|\boldsymbol{\beta}_j-\sigma_j^i|=x+(n-2)\frac{x}{n}
|
||
$$
|
||
|
||
所以
|
||
|
||
$$
|
||
\frac{\sum\limits_{i=0}^{n}|\boldsymbol{\beta}_j-\sigma_j^i|}{\sum\limits_{i=0}^{n}|\boldsymbol{\mu}_j-\sigma_j^i|}=1+\frac{n-2}{n}\leq 2
|
||
$$
|
||
|
||
得证
|
||
|
||
### T1.3
|
||
|
||
$$
|
||
d(\boldsymbol{\sigma^{\prime}},\boldsymbol{\Sigma}) = \sum\limits_{i=1}^{k}L_1(\boldsymbol{\sigma^{\prime}},\boldsymbol{\sigma})\leq \sum\limits_{i=1}^{k}L_1(\boldsymbol{\sigma^{\prime}},\boldsymbol{\mu}) + \sum\limits_{i=1}^{k}L_1(\boldsymbol{\mu},\boldsymbol{\sigma})
|
||
$$
|
||
|
||
$$
|
||
\leq \sum\limits_{i=1}^{k}L_1(\boldsymbol{\sigma}^*,\boldsymbol{\mu}) + \sum\limits_{i=1}^{k}L_1(\boldsymbol{\mu},\boldsymbol{\sigma})
|
||
$$
|
||
|
||
$$
|
||
\leq \sum\limits_{i=1}^{k}L_1(\boldsymbol{\sigma}^*,\boldsymbol{\sigma}) + \sum\limits_{i=1}^{k}L_1(\boldsymbol{\sigma},\boldsymbol{\mu}) + \sum\limits_{i=1}^{k}L_1(\boldsymbol{\mu},\boldsymbol{\sigma})
|
||
$$
|
||
|
||
$$
|
||
= \sum\limits_{i=1}^{k}L_1(\boldsymbol{\sigma}^*,\boldsymbol{\sigma}) + 2\sum\limits_{i=1}^{k}L_1(\boldsymbol{\mu},\boldsymbol{\sigma})
|
||
$$
|
||
|
||
$$
|
||
= d(\boldsymbol{\sigma}^*,\boldsymbol{\Sigma}) + 2d(\boldsymbol{\mu},\boldsymbol{\Sigma})
|
||
$$
|
||
|
||
$$
|
||
\leq 3d(\boldsymbol{\sigma}^*,\boldsymbol{\Sigma})
|
||
$$
|
||
|
||
同理，由T1.2知
|
||
|
||
$$
|
||
\sum\limits_{i=0}^{n}|\boldsymbol{\beta}_j-\sigma_j^i|\leq 2 \sum\limits_{i=0}^{n}|\boldsymbol{\mu}_j-\sigma_j^i|
|
||
$$
|
||
|
||
$$
|
||
d(\boldsymbol{\sigma^{\prime}},\boldsymbol{\Sigma}) = \sum\limits_{i=1}^{k}L_1(\boldsymbol{\sigma^{\prime}},\boldsymbol{\sigma})\leq \sum\limits_{i=1}^{k}L_1(\boldsymbol{\sigma^{\prime}},\boldsymbol{\beta}) + \sum\limits_{i=1}^{k}L_1(\boldsymbol{\beta},\boldsymbol{\sigma})
|
||
$$
|
||
|
||
$$
|
||
\leq \sum\limits_{i=1}^{k}L_1(\boldsymbol{\sigma}^*,\boldsymbol{\sigma}) + 2\sum\limits_{i=1}^{k}L_1(\boldsymbol{\beta},\boldsymbol{\sigma})
|
||
$$
|
||
|
||
$$
|
||
\leq \sum\limits_{i=1}^{k}L_1(\boldsymbol{\sigma}^*,\boldsymbol{\sigma}) + 4\sum\limits_{i=1}^{k}L_1(\boldsymbol{\mu},\boldsymbol{\sigma})
|
||
$$
|
||
|
||
$$
|
||
\leq 5d(\boldsymbol{\sigma}^*,\boldsymbol{\Sigma})
|
||
$$
|
||
|
||
得证
|
||
|
||
## T2
|
||
|
||
### T2.1
|
||
|
||
$\boldsymbol{S}=(7,8,-10,-5)^T$
|
||
|
||
### T2.2
|
||
|
||
$\boldsymbol{S^{(2)}}=(37,-7,-17,-5)^T$
|
||
|
||
### T2.3
|
||
|
||
$$
|
||
s^i = \sum\limits_{j\in T_i}q_{ij}
|
||
$$
|
||
|
||
在讨论 $\boldsymbol{S}^{(2)}$ 的计算时，
|
||
|
||
对于每个 $s^{(2)}_i$ 我们首先考虑单个 $j$ 的情况，对于 $\forall k \in T_j$ , $q^{(2)}_{ik} = q_{ij}+q_{jk}$，所以
|
||
|
||
$$
|
||
q^{(2)}_{ik} = \sum\limits_{k \in T_j}q_{ij}+q_{jk} = lq_{ij} + s_j
|
||
$$
|
||
|
||
所以，$s^{(2)}_i$ 即为上式求和
|
||
|
||
$$
|
||
s^{(2)}_i = \sum\limits_{j \in T_i}lq_{ij}+s_j = \sum\limits_{j=0}^{n}m_{ij}(s_j+q_{ij}l) = \sum\limits_{j=0}^{n}m_{ij}s_j + s_il
|
||
$$
|
||
|
||
如此求出每个 $s^{(2)}_i$，即可得到 $\boldsymbol{S}^{(2)}$
|
||
|
||
$$
|
||
\boldsymbol{S}^{(2)}=(\boldsymbol{M}+l*\boldsymbol{E})\boldsymbol{S}
|
||
$$
|
||
|
||
对于 $\boldsymbol{M}^2$ 若 $m^2_{ik}\neq 0$ ，则必然 $\exist j$ 使得 $m_{ij}m_{jk} = 1$所以 $m^2_{ik}$ 的值即为 $j$ 的个数，即为 $i$ 与 $k$ 之间发生的间接比赛的场数
|
||
|
||
所以 $\boldsymbol{M}^2$ 保存了所有间接比赛的场数
|
||
|
||
### T2.4
|
||
|
||
我们易知
|
||
|
||
$$
|
||
\boldsymbol{S}^{(3)}=\boldsymbol{M}\boldsymbol{S}^{(2)}+l^2\boldsymbol{S}
|
||
$$
|
||
|
||
$$
|
||
\boldsymbol{S}^{(n)}=\boldsymbol{M}\boldsymbol{S}^{(n-1)}+l^{n-1}\boldsymbol{S}
|
||
$$
|
||
|
||
所以递推得到
|
||
|
||
$$
|
||
\boldsymbol{S}^{(n)}=\boldsymbol{M}^{n-1}\boldsymbol{S} + (\boldsymbol{M}^{n-1}-l^{n-1}\boldsymbol{E})(\boldsymbol{M}-l\boldsymbol{E})^{-1}l\boldsymbol{S}
|
||
$$
|