\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage[hidelinks]{hyperref}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{textcomp}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\setlength{\headheight}{0pt}
\geometry{left=2.5cm,right=2.5cm,headsep=2cm,bottom=2cm,footnotesep=2cm}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{
    \begin{huge}
        \textbf{}
    \end{huge}\\
    \vspace{0.4cm}
    \ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年10月11日}

\ctexset{
    section={
      format+ = \Large \raggedright,
     }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{arrows}

\newcounter{aufgc}
\newenvironment{exercise}[1]%
{\refstepcounter{aufgc}\textbf{问题 \arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\begin{document}

\textbf{Q1.}

\begin{proof}
    要产生一个比 $1-\alpha:\alpha$ 更不平衡的划分，则需要选取的
    pivot 要处于整个数组中的低 $\alpha$ 或高 $\alpha$ 部分，则
    只需在剩下部分中选取就能更平衡，对应概率约为 $1-2\alpha$.
\end{proof}

\hrulefill\medskip

\textbf{Q2.}

(1) 只需在算法 SELECT 基础上作一定修改即可，算法如下，其中前4步均
和 SELECT 没有区别.

\begin{itemize}
    \item [1.] 将数组的 $n$ 个元素划分为 $\lceil n/5\rceil$ 组，
          每组 $5$ 个元素，且至多只有一组由剩下的 $n\mod 5$ 个元
          素组成.
    \item [2.] 寻找这 $\lceil n/5\rceil$ 组中每一组的中位数：首
          先对每组元素使用插入排序，然后确定每组有序元素的中位数.
    \item [3.] 对第2步中找出的 $\lceil n/5\rceil$ 个中位数，递归
          调用 SELECT 以找出其中位数 $x$，如果有偶数个中位数，约定 $x$
          是较小的中位数.
    \item [4.] 利用修改过的 PARTITION 版本，按中位数的中位数 $x$
          对输入数组进行划分.
    \item [5.] 计算 $\sum_{x_i<x}w_i$ 和 $\sum_{x_i>x}w_i$，如果
          两个结果均不大于 $\frac{1}{2}\sum_{i=1}^{n}w_i$，则返回 $x$，
          否则如果 $\sum_{x_i<x}w_i$ 更大，则递归查找 $x$ 的左侧，否则
          递归查找 $x$ 的右侧.
\end{itemize}

因为相比原本的版本只是在第5步里多了一个 $O(n)$ 的计算，所以并不破坏
原本的最坏时间复杂度为 $O(n)$ 这一性质.

(2) 首先从 $n=1$ 到 $T-1$ 依次计算出 $\Delta^2\{b_n\}=\Delta\{b_{n+1}\}-\Delta\{b_n\}=\Delta\{a_n\}$，
考虑到 $\Delta\{b_T\}=b_{T+1}-b_T=b_1-b_T$，因此有 $\sum_{n=1}^{T}\Delta\{b_n\}=0$，
一共 $T$ 个方程，$T$ 个未知数，且可以在 $O(T)$ 时间内通过
前 $T-1$ 个方程用 $\Delta\{b_1\}$ 表示出 $\Delta\{b_2\},\ldots,\Delta\{b_T\}$，
再代入第 $T$ 个方程就可以得出所有的 $\Delta\{b_n\}$.

之后使用第 (1) 问的算法在 $O(T)$ 时间内求数列 $0,\Delta\{b_1\},\Delta\{b_1\}+\Delta\{b_2\},\ldots,\sum_{k=1}^{T-1}\Delta\{b_k\}$
以 $1,1,\ldots,1$ 为权的加权平均差.

可以分析其最坏时间复杂度为 $O(T)$.

\hrulefill\medskip

\textbf{Q3.}

(1) 算法伪代码见算法~\ref{algo:1}. 因为只将两个数组遍历了一遍，所以最坏也是线性的.

\begin{algorithm}[htbp]
    \caption{线性时间复杂度求 $|S|$}\label{algo:1}
    \SetKw{kwand}{and}
    $i\leftarrow1$\;
    $j\leftarrow1$\;
    $cnt\leftarrow0$\;
    \While{$i<n$ \kwand$j<m$}{
    \eIf{$A[i]>B[j]$}{
    $j\leftarrow j+1$\;
    }{
    $cnt\leftarrow cnt+j-1$\;
    $i\leftarrow i+1$\;
    }
    }
    \While{$i<n$}{
        $cnt\leftarrow cnt+j-1$\;
        $i\leftarrow i+1$\;
    }
    \Return{$cnt$}\;
\end{algorithm}

(2) 修改归并排序的算法得到算法~\ref{algo:2}，可以看出相比原本的归并
排序只在每次比较中多了 $O(1)$ 的计算，因此不改变原本的最坏时间复杂度
$O(n\lg n)$.

\begin{algorithm}[htbp]
    \caption{利用归并排序求 $|I|$}\label{algo:2}
    \SetKwProg{Fn}{Function}{:}{}
    \SetKwFunction{Cnt}{Count}
    \SetKwFunction{Mer}{Merge}
    $|I|=$ \Cnt{$L,1,n$}\;
    \Fn{\Cnt{$L, p, r$}}{
        \If{$p<r$}{
            $q\leftarrow\lfloor(p+r)/2\rfloor$\;
            $cnt\leftarrow$ \Cnt{$L, p, q$} $+$ \Cnt{$L, q+1, r$}\;
            \Return{\Mer{$L, p, q, r$} $+\ cnt$}\;
        }
        \Return{$0$}\;
    }
    \Fn{\Mer{$L,p,q,r$}}{
        $n_1\leftarrow q-p+1$\;
        $n_2\leftarrow r-q$\;
        Let $A[1..n_1+1]$ and $B[1..n_2+1]$ be new arrays\;
        \For{$i\leftarrow 1$ \KwTo$n_1$}{
            $A[i]\leftarrow L[p+i-1]$\;
        }
        \For{$j\leftarrow 1$ \KwTo$n_2$}{
            $B[j]\leftarrow L[q+j]$\;
        }
        $A[n_1+1]\leftarrow\infty$\;
        $B[n_2+1]\leftarrow\infty$\;
        $i\leftarrow 1$\;
        $j\leftarrow 1$\;
        $inv\leftarrow 0$\;
        \For{$k\leftarrow p$ \KwTo$r$}{
            \eIf{$A[i]\leqslant B[j]$}{
                $L[k]\leftarrow A[i]$\;
                $i\leftarrow i+1$\;
            }{
                $inv\leftarrow inv+n_1-i+1$\;
                $L[k]\leftarrow B[j]$\;
                $j\leftarrow j+1$\;
            }
        }
        \Return{$inv$}\;
    }
\end{algorithm}

(3)
\begin{proof}
    假设不存在 $A$ 的两个排列 $A_1,A_2$ 只相差一次对换，且服从于 $C$，
    也就是 $A$ 的某一个排列服从于 $C$，但无论将其的哪两个元素进行
    对换得到的结果均不服从于 $C$，也就是 $C$ 中至少含有 $C_n^2$ 个元素，
    即 $\forall i\neq j\in A,\langle i,j\rangle\in C\lor\langle j,i\rangle\in C$.

    但在已知了 $C_n^2$ 个大小关系后，无法将 $A$ 的元素作重新排列且服从
    于 $C$，与题设矛盾，因此原命题成立，即一定存在 $A$ 的两个排列 $A$
    的两个排列 $A_1,A_2$，都服从于 $C$，且只相差一次对换.
\end{proof}

(4)
\begin{proof}
    因为同一个数组的两个排列只相差一次对换时，均服从 $C$，但做了一次
    对换之后两排列的逆序数相差 $1$，因此如果不得到排序时无法得到准确
    的时间复杂度，而基于比较的排序算法以 $\Omega(n\lg n)$ 为时间复
    杂度下界，因此对于 (2) 中的问题，基于比较的算法具有 $\Omega(n\lg n)$.
    的最坏时间复杂度下界.
\end{proof}

\hrulefill\medskip

\textbf{Q4.}

(1) 是完备的，因为四种算法种每个元素均可能出现在任意一个位置，所以
完备.

(2) 第4个是均匀的，其他均是不均匀的. 因为 $n$ 个数排列一共有 $n!$
种可能，而第一个算法共有 $n^n$ 种可能的结果，第二个算法有
$2^{n(n-1)}$ 种可能的结果，第三个算法有 $n^{2n}$ 种可能的结果，均
不能被 $n!$ 整除，因此不能是均匀的.

算法4每次从未选定的部分中随机选一个放在前面，之后不再移动，因此一共
有 $n\times (n-1) \times\cdots 1=n!$ 种可能，因此是均匀的.

(3.1) 错误，如上前三种算法，均完备且每个元素被打乱到任意一个位置的
概率均为 $\frac{1}{n}$，但不是均匀的.

(3.2) 正确，只需重复 $n!$ 次总能趋于均匀.

(4) 算法1先猜测 JKQ, QJK, QKJ，再猜测 JQK, KJQ, KQJ，期望猜测次
数为 10/3 次.

算法2先猜测 JQK, JKQ, QJK, QKJ，再猜测 KJQ, KQJ，期望猜测次数为 55/16 次.

算法3先猜测 JQK，再猜测 JKQ, QJK, KQJ，最后猜测 QKJ, KJQ，期望猜测次数为 91/27 次.

因为均匀，算法4只需依次尝试6次不同的排列即可，期望猜测次数为3.5次.

(5) 不会

\hrulefill\medskip

\textbf{Q5.}

(1) \begin{proof}
    首先证明传递性，即 \[\langle x_1,\ldots,x_m\rangle\lesssim_m\langle y_1,\ldots,y_m\rangle \land\langle y_1,\ldots,y_m\rangle\lesssim_m\langle z_1,\ldots,z_m\rangle\Rightarrow\langle x_1,\ldots,x_m\rangle\lesssim_m\langle z_1,\ldots,z_m\rangle\]
    假如 $\bigwedge_{i=1}^{m}x_i\sim y_i$，则因为 $\langle y_1,\ldots,y_m\rangle\lesssim\langle z_1\ldots,z_m\rangle$
    有 $\langle x_1,\ldots,x_m\rangle\lesssim\langle z_1,\ldots,z_m\rangle$；

    否则 $\exists i<m,x_{i+1}<y_{i+1}\land(\bigvee_{j=1}^{i}x_j\sim y_j)$，

    在 $\bigwedge_{i=1}^{m}y_i\sim z_i$ 时，$\exists i<m,x_{i+1}<z_{i+1}\land(\bigvee_{j=1}^{i}x_j\sim z_j)$，$\langle x_1,\ldots,x_m\rangle\lesssim_m\langle z_1,\ldots,z_m\rangle$

    在 $\exists t<m,y_{t+1}<z_{t+1}\land(\bigvee_{j=1}^{t}y_j\sim z_j)$时，

    若 $i\leqslant t$，则 $\forall j\leqslant i,x_j\sim y_j,y_j\sim z_j\Rightarrow x_j\sim z_j$，且 $x_{i+1}<y_{i+1},y_{i+1}\sim z_{i+1}\Rightarrow x_{i+1}<z_{i+1}$，

    若 $i>t$，则 $\forall j\leqslant t,x_j\sim y_j,y_j\sim z_j\Rightarrow x_j\sim z_j$，且 $x_{t+1}\sim y_{t+1},y_{t+1}< z_{t+1}\Rightarrow x_{t+1}<z_{t+1}$，

    综上所述，传递性得证.

    接着证明强连接性，即 \[\forall \langle x_1,\ldots,x_m\rangle,\langle y_1,\ldots,y_m\rangle,\langle x_1,\ldots,x_m\rangle\lesssim_m\langle y_1,\ldots,y_m\rangle\lor\langle y_1,\ldots,y_m\rangle\lesssim_m\langle x_1,\ldots,x_m\rangle\]
    不妨假设 $\forall j\leqslant i< m,x_j\sim y_j$，而对 $x_{i+1}$ 和 $y_{i+1}$ 的关系，

    要么 $x_{i+1}<y_{i+1}$，则 $\langle x_1,\ldots,x_m\rangle\lesssim_m\langle y_1,\ldots,y_m\rangle$，

    要么 $x_{i+1}>y_{i+1}$，则 $\langle y_1,\ldots,y_m\rangle\lesssim_m\langle x_1,\ldots,x_m\rangle$，

    要么 $x_{i+1}\sim y_{i+1}$，则化归为以上的情况，除了 $\forall j\leqslant m,x_j\sim y_j$，则也一样有 $\langle x_1,\ldots,x_m\rangle\lesssim_m\langle y_1,\ldots,y_m\rangle$，
    因此强连接性得证.

    综合传递性和强连接性，$\lesssim_m$ 是 $X^m$ 上的全预序.

\end{proof}

(2.1) 先对同构意义下的全预序作讨论，考虑等价关系，两两不等价的只有
一种，而只有一对等价的有4种，两对两两等价的有3种，一对3等价的有3种，
一对4等价的有2种，一对2等价一对3等价的有2种，全等价的只有1种，总共16种.

不考虑同构，则有 $1\times5!+4\times C_5^2\times3!+3\times C_5^2C_3^2+3\times C_5^3\times 2!+2\times C_5^4+2\times C_5^3+1=541$ 种全预序.

(2.2) 选取全预序使得 $a\sim b,c\sim d,a\lesssim b\lesssim c\lesssim d\lesssim e$，
则有 $<_1$ 对应哈斯图如下

\begin{tikzpicture}[scale=.7]
    \node (e) at (0,2) {$e$};
    \node (d) at (1,0) {$d$};
    \node (c) at (-1,0) {$c$};
    \node (b) at (1,-2) {$b$};
    \node (a) at (-1,-2) {$a$};
    \draw (c) -- (e) -- (d) -- (b) -- (c) -- (a) -- (d);
\end{tikzpicture}

而 $<_2$ 对应哈斯图如下

\begin{tikzpicture}[scale=.7]
    \node (ee) at (0,8) {$(e,e)$};
    \node (ed) at (1,6) {$(e,d)$};
    \node (ec) at (-1,6) {$(e,c)$};
    \node (eb) at (1,4) {$(e,b)$};
    \node (ea) at (-1,4) {$(e,a)$};
    \node (de) at (1,2) {$(d,e)$};
    \node (ce) at (-1,2) {$(c,e)$};
    \node (dd) at (3,0) {$(d,d)$};
    \node (dc) at (1,0) {$(d,c)$};
    \node (cd) at (-1,0) {$(c,d)$};
    \node (cc) at (-3,0) {$(c,c)$};
    \node (db) at (3,-2) {$(d,b)$};
    \node (da) at (1,-2) {$(d,a)$};
    \node (cb) at (-1,-2) {$(c,b)$};
    \node (ca) at (-3,-2) {$(c,a)$};
    \node (be) at (1,-4) {$(b,e)$};
    \node (ae) at (-1,-4) {$(a,e)$};
    \node (bd) at (3,-6) {$(b,d)$};
    \node (bc) at (1,-6) {$(b,c)$};
    \node (ad) at (-1,-6) {$(a,d)$};
    \node (ac) at (-3,-6) {$(a,c)$};
    \node (bb) at (3,-8) {$(b,b)$};
    \node (ba) at (1,-8) {$(b,a)$};
    \node (ab) at (-1,-8) {$(a,b)$};
    \node (aa) at (-3,-8) {$(a,a)$};
    \draw (ec) -- (ee) -- (ed) -- (ea) -- (ec) -- (eb) -- (ce) -- (ea) -- (de) -- (cc) -- (ce) -- (cd) -- (de) -- (dc) -- (ce) -- (dd) -- (ca) -- (cc) -- (cb) -- (cd) -- (ca) -- (dc) -- (cb) -- (dd) -- (da) -- (dc) -- (db) -- (cc) -- (da) -- (cd) -- (db) -- (ae) -- (ca) -- (be) -- (cb)
    -- (ae) -- (da) -- (be) -- (ac) -- (ae) -- (ad) -- (be) -- (bc) -- (ae) -- (bd) -- (aa) -- (ac) -- (ab) -- (ad) -- (aa) -- (bc) -- (ab) -- (bd) -- (ba) -- (ac) -- (bb) -- (ad) -- (ba) -- (bc) -- (bb) -- (bd) -- (be) -- (db) -- (dd) -- (de) -- (eb) -- (ed);

\end{tikzpicture}

商集 $X/\sim=\{\{a,b\},\{c,d\},\{e\}\}$，
\begin{align}
    X^2/\sim_2=\{ & \{(a,a),(a,b),(b,a),(b,b)\},\{(a,c),(a,d),(b,c),(b,d)\},\{(a,e),(b,e)\}, \nonumber \\
                  & \{(c,a),(c,b),(d,a),(d,b)\},\{(c,c),(c,d),(d,c),(d,d)\},\{(c,e),(d,e)\}, \nonumber \\
                  & \{(e,a),(e,b)\},\{(e,c),(e,d)\},\{(e,e)\}\} \nonumber
\end{align}

(3) 首先使用堆排序对 $X$ 中的元素在 $\lesssim$ 意义下作排序，这样
最坏的时间复杂度为 $O(|X|\lg|X|)$，每个元素的下标从 $0$ 到 $|X|-1$.

作一轮循环，得到 $|X|,|X|^2,\ldots,|X|^m$，时间复杂度为 $O(m)$.

接着取 $\lfloor k/|X|^{m-1}\rfloor$ 为下标的元素作为所求元素的最
高维，对应余数 $k'$，再取 $\lfloor k'/|X|^{m-2}\rfloor$ 为下标的
元素作为所求元素的次高位，这样循环直至最后的余数为下标的元素作为所
求元素的最低位，得到元素即为所求，这样最坏的时间复杂度为 $O(m)$.

因此总的最坏时间复杂度为 $O(m+|X|\lg |X|)$.

\end{document}