\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}

\geometry{left=2.5cm,right=2.5cm,headsep=1cm,bottom=2cm,footnotesep=2cm,headheight=13pt}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{\ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年3月18日}

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

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

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{arrows}

\DeclareMathOperator*{\E}{\mathbb{E}}

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

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


\begin{document}
\begin{exercise}{分析程序，证明下面的问题}
	\begin{algorithm}
		\caption{Quick Sort algorithm}\label{alg:sampling1}
		\SetKwFunction{QS}{QSort}
		\SetKwFunction{Sw}{Swap}
		\SetKwProg{Fn}{Function}{:}{end\ Function}
			\Fn{\QS{$l,r$}}{
				\If{$l\geqslant r$}{
					\textbf{exit}
				}
				pick a random element in $A[l], \ldots, A[r]$ as $pivot$\\
				$i=l, j=r$\\
				\While{$i\leqslant j$}{
					\While{$A[i] < pivot$} {$i=i+1$}
					\While{$A[j] > pivot$} {$j=j-1$}
					\If{$i \leqslant j$}{
						\Sw{$A[i], A[j]$}\\
						$i=i+1$\\
						$j=j-1$
					}
				}				
				\QS{$l, j$}\\
				\QS{$i, r$}
			}			
	\end{algorithm}

	(a) 证明\textsc{QSort} ($1,n$)算法的正确性.\\
	(b) 用递归公式分析算法的期望运行时间为$O(n\log(n))$.%(如果用到数学归纳法，需要保证$O(n)$中的系数在归纳时不变化，参考教材$P48$)\\ 
\end{exercise}

\begin{proof}
	首先，经过一轮循环\verb|while|，得到的数列中下标比$j$小的都小于$pivot$，下标比$i$大的都大于$pivot$. \\
	然后，对于下标比$j$小的数列，递归调用\verb|QSort|，对于下标比$i$大的数列，递归调用\verb|QSort|.\\
	最后，由于每次递归调用\verb|QSort|都会将数列分成两个部分，因此，每次递归调用的时间复杂度为$O(n)$，因此，总的时间复杂度为$O(n\log(n))$.\\
	递归公式为\[T(n)=2T(\frac{n}{2})+O(n)\]
\end{proof}
	
\hrulefill\vspace{0.2cm}
		
\begin{exercise}{归并排序算法如下，试改进归并算法，计算逆序对数目 (存在正整数 $i, j$ 使得 $1 \leqslant i < j \leqslant n$而且 $A[i] > A[j]$，则 $\langle A[i], A[j]\rangle$ 称为 $A$ 的一个逆序对).}
	\begin{algorithm}[H]
		\caption{Merge Sort algorithm}\label{alg:sampling2}
		\SetKwProg{Fn}{Function}{:}{end\ Function}
		\SetKwFunction{Me}{Merge}
		\SetKwFunction{St}{Sort}
		\Fn{\Me{$p,j,k$}}{
			$n_1 = j-p$, $n_2 = k-j+1$\\
			Let $L[1, \ldots, n_1+1]$ and $R[1, \ldots, n_2+1]$ be new arrays to avoid shift\\
			$L[i] = A[p+i-1]$ for $i \leqslant n_1$ and $L[n_1+1] = \infty$\\
			$R[i] = A[j+i-1]$ for $i \leqslant n_2$ and $R[n_2+1] = \infty$\\
			$i_l = 1$, $i_r = 1$\\
			\For{$i = p, \ldots, k$}{
				\eIf{$L[i_l] \leqslant R[i_r]$}{
					$A[i] = L[i_l]$\\
					$i_l = i_l +1$
				}{
					$A[i] = R[i_r]$\\
					$i_r = i_r+1$
				}
			}
		}
			
		\Fn{\St{$p,r$}}{
			\If{$p < r$}{
				$q = \frac{p+r}{2}$\\
				\St{$p, q$}\\
				\St{$q+1, r$}\\
				\Me{$p, q+1, r$}
			}
		}	
	\end{algorithm}
\end{exercise}

\textit{解.}见算法\ref{alg:inversion}.

其正确性依据归并排序的正确性，\verb|Merge|中每次比较时，若$A[i] > A[j]$，则$A[i+1], \ldots, A[j-1]$都大于$A[j]$，因此，逆序对数目为$j-i$.
同时因为最初\verb|Merge|时比较是相邻元素两两进行的，因此每次的\verb|Merge|中下标$q$前和$q$后的元素均已被排序正确，无需担心逆序对数目的计算错误.

\begin{algorithm}
	\caption{inversion algorithm}\label{alg:inversion}
	\SetKwProg{Fn}{Function}{:}{end\ Function}
	\SetKwFunction{Me}{Merge}
	\SetKwFunction{St}{Count}
	\Fn{\Me{$p,j,k$}}{
		$n_1 = j-p$, $n_2 = k-j+1$\\
		Let $L[1, \ldots, n_1+1]$ and $R[1, \ldots, n_2+1]$ be new arrays to avoid shift\\
		$L[i] = A[p+i-1]$ for $i \leqslant n_1$ and $L[n_1+1] = \infty$\\
		$R[i] = A[j+i-1]$ for $i \leqslant n_2$ and $R[n_2+1] = \infty$\\
		$i_l = 1$, $i_r = 1$\\
		$cnt=0$\\
		\For{$i = p, \ldots, k$}{
			\eIf{$L[i_l] \leqslant R[i_r]$}{
				$A[i] = L[i_l]$\\
				$i_l = i_l +1$
			}{
				$A[i] = R[i_r]$\\
				$i_r = i_r+1$\\
				$cnt=cnt+j+i_r-p-i_l$
			}
		}
		\KwRet{cnt}
	}
		
	\Fn{\St{$p,r$}}{
		$cnt=0$\\
		\If{$p < r$}{
			$q = \frac{p+r}{2}$\\
			\St{$p, q$}\\
			\St{$q+1, r$}\\
			$cnt=cnt+$\Me{$p, q+1, r$}
		}
		\KwRet{cnt}
	}	
\end{algorithm}
	
\newpage

\begin{exercise}{给定两个排好序的长为$ n $的数组$ X[1\dots n] $和$ Y[1\dots n] $}
	(a) 给定一个键值$key$，设计算法在$ O(\log n) $时间内找出$X$中小于等于$key$的元素个数；并分析算法的正确性.\\
	(b) 给定一个整数$ k \in [1, n]$，设计算法在$ O(\log n) $时间内找到$ X $和$ Y $一共$ 2n $个元素中第$ k $大的元素；并分析算法的正确性.
\end{exercise}

\textit{解.}

(a)设计算法如算法\ref{alg:count1}所示.因为已经排序好，因此每次选取在$l$和$r$中间位置的元素与$key$进行比较，如果其值比$key$大，则小于等于$key$的元素个数只能是在$l$和$pivot$之间的元素个数，否则则是在$pivot$和$r$之间的元素个数加上$pivot-l+1$，即从$l$到$pivot$之间的元素个数.

\begin{algorithm}[H]
	\caption{Merge Sort algorithm}\label{alg:count1}
	\SetKwProg{Fn}{Function}{:}{end\ Function}
	\SetKwFunction{Ct}{Count}
	\Fn{\Ct{$l,h$}}{
		\If{$l\geqslant h$}{
			\KwRet{$0$}
		}
		$pivot=(l+h)/2$\\
		\eIf{$X[pivot]\geqslant key$}{
			\KwRet{\Ct{$l,pivot$}}
		}{
			\KwRet{$pivot-l+1+$\Ct{$pivot+1,h$}}
		}
	}
	\Ct{$1,n$}
\end{algorithm}

(b)设计算法如算法\ref{alg:count2}所示

\begin{algorithm}[H]
	\caption{Merge Sort algorithm}\label{alg:count2}
	\SetKwProg{Fn}{Function}{:}{end\ Function}
	\SetKwFunction{Ct}{Count}
	\Fn{\Ct{$l,h$}}{
		\If{$l\geqslant h$}{
			\KwRet{$0$}
		}
		$pivot=(l+h)/2$\\
		\eIf{$X[pivot]\geqslant key$}{
			\KwRet{\Ct{$l,pivot$}}
		}{
			\KwRet{$pivot-l+1+$\Ct{$pivot+1,h$}}
		}
	}
	\Ct{$1,n$}
\end{algorithm}

\newpage

\begin{exercise}{参考算法导论第8.1章，考虑$\sigma$为$n$个未知元素所有$ n! $个排列中均匀随机产生的.}
	(a) 对任何基于比较排序的确定性算法$A$，证明对至少99\%的全排列，$A$的运行时间为$\Omega(n \log n)$.也就是
		\[
		\Pr_{\sigma}\left[Time \bigg( A(\sigma) \bigg) \geqslant 0.5 n \log n \right] \geqslant 0.99.
		\]
		其中$ Time(A(\sigma)) $表示算法$ A $的运行时间.\\
	(b) 考虑任一基于比较排序的随机化算法 $ A $ （永远输出正确答案，但运行时间为随机变量），证明类似的结论：
		\[ \Pr_{\sigma} \left[ \E_r\bigg[Time\big( A(\sigma, r) \big) \bigg] \geqslant 0.5 n \log n  \right]\geqslant 0.99.\]
		\textbf{提示：}假定算法$ A $采用固定长度$ l $的随机数$ r $，那么$ r\in {\{0, 1\}}^l $.在随机数$ r $确定之后，$ A(\cdot , r) $就是一个确定性的算法.
\end{exercise}

\end{document}
