\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{hyperref}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\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年3月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}

\begin{exercise}{考虑如下的求幂次的算法，给出该算法最紧的时间复杂度
    $(\Theta)$，这是线性时间的吗？如果不是，能否给出线性时间的算法，
    需要说明给出算法的正确性.}
    \begin{algorithm}
        \caption{\textsc{Power}($n,k,q$)}
        \SetKw{KwReturn}{return}
        \KwIn{$n\in\mathbb{R}$,$k\in\mathbb{Z}^+$,$q\in\mathbb{Z}^+$}
        \KwOut{$n^k\mod q$}
        $m = 1$\\
        \For{$i=1$ \KwTo $k$}{
            $m=m\cdot n\mod q$}
        \KwReturn{m}
    \end{algorithm}
\end{exercise}

\textit{解.} 易知，若乘法和取模运算时间复杂度均为$O(1)$，则所需时间
为$O(1)+k\cdot O(1)=O(k)$，为线性时间复杂度.

假如考虑$n\in\mathbb{R}$，实数乘法取模的时间复杂度可能更高，比如与
位数为线性的即$O(\log n)$，则该算法时间复杂度为$O(k\cdot \log n)$
是线性对数时间复杂度.

以下为在这样前提下的线性时间复杂度算法.

\begin{algorithm}
    \caption{\textsc{Power}$(n,k,q)$}
    \caption{\textsc{Power}($n,k,q$)}
        \SetKw{KwReturn}{return}
        \KwIn{$n\in\mathbb{R}$,$k\in\mathbb{Z}^+$,$q\in\mathbb{Z}^+$}
        \KwOut{$n^k\mod q$}
        $m = 1$\\
        $s = n \mod q$\\
        \While{$k\neq 0$}{
            \If{$k\mod 2=1$}{
                $m = m\cdot s\mod q$
            }
            $k=\lfloor k/2\rfloor$\\
            $s = s^2 \mod q$
        }
        \KwReturn{m}
\end{algorithm}

其时间复杂度为$O(\log n)+\log k*O(\log n)=O(\log k*\log n)\sim O(n)$
为线性时间

下证算法正确性：

\begin{proof}
    若$k=0$，则不执行循环体，$m=1=n^0\mod q$，显然成立.
    
    有以下事实：$(m\mod q)\cdot a\mod q=m\cdot a\mod q$（假设$m=tq+p,t\in \mathbb{Z},0\leqslant p<q$，则$(m\mod q)\cdot a\mod q=p\cdot a\mod q$而$m\cdot a\mod q=(tq\cdot a+p\cdot a)\mod q=p\cdot a\mod q$）

    通过二进制转化，对每一个$k>0$，有$k=\sum_{i=0}^{\lceil\log k\rceil}a_i2^i,a_i\in\{0,1\}$
    因此\[n^k\mod q=n^{\sum_{i=0}^{\lceil\log k\rceil}a_i2^i}\mod q=(\prod_{a_i\neq0}n^{2^i})\mod q\]
    算法中$k\mod 2=1$时对应$a_i=1$，则将对应的$s^{2^i}$与总乘积$m$
    相乘最终得到的结果就是所求.
\end{proof}

注：实际原问题算法是\textbf{有问题的}!因为$a\in \mathbb{R}$时
，前述事实证明中$tq\cdot a\mod q= 0$并不一定成立，因此
$(m\mod q)\cdot a\mod q\neq m\cdot a\mod q$.随便取一个反例如
$n=1.3,k=10,q=1$，按算法运行得到的结果约为$0.325$，实际结果应为$
0.786$.因此$n\in\mathbb{R}$应改为$\mathbb{Z}$才能保证算法的正确性.

\hrulefill\medskip

\begin{exercise}{
    \emph{(a)}假设有$n$个球，将其分别随机投入$N$个盒子中，即每个球以
    $\frac{1}{N}$的概率被投入到其中一个盒子中.假设$N\geqslant n$，
    试求每个盒子中至多有一个球的概率.\\    
    \emph{(b)}重复扔一枚不一定均匀的硬币，即该硬币会以$p$的概率正面
    朝上，试求第一次出现正面朝上的所扔硬币次数的期望.}
\end{exercise}

\textit{解.}

(a)由题，$n$个球，每个球有$N$个可能，则共有$N^n$种放球的方案，而每个
盒子至多一个球，则为对$N$个盒子求长为$n$的排列，即所求概率为
\[P=\frac{N(N-1)\cdots(N-n+1)}{N^n}\]

(b)设扔到第$X$次才第一次出现硬币正面朝上，有
\[P(X=k)=p(1-p)^{k-1},k=1,2,\ldots\]
则所求期望为
\[EX=\sum_{k=1}^\infty kp(1-p)^{k-1}=-p\left(\sum_{k=0}^\infty (1-p)^k\right)^\prime=-p\cdot \left(\frac{1}{1-(1-p)}\right)^\prime=\frac{1}{p}\]

\hrulefill\medskip

\begin{exercise}{给出辗转相除法的时间复杂度上界，写出详细分析过程.
    默认所有整数运算的时间皆为$O(1)$.以下为辗转相除法伪代码.}

    \begin{algorithm}
        \caption{\textsc{Euclid}($a$, $b$)}
        \SetKw{KwReturn}{return}
        \eIf{$b=0$}{
            \KwReturn{a}
        }{
            \KwReturn{\textsc{Euclid}($b$, $a\mod b$)}
        }
    \end{algorithm}
\end{exercise}

\textit{解.} 当$b\neq0$时，原问题化为一个比$b$还要小的问题.当
$b\geqslant a/2$时，$a\mod b=a-b\leqslant a-a/2=a/2$；当$b<a/2$时
，$a\mod b<b<a/2$，因此每次迭代问题规模至多为原来的一半，算法时间复
杂度上界为对数阶$O(\log a)$.

\hrulefill\medskip

\begin{exercise}{在课上我们观察到了 Shell Sort 的一个重要性质：\\
    一旦对数组$A$调用了步长为$h$的选择排序，$A$数组在 Shell Sort 的
    未来时刻总是有\emph{(注：此处的未来时刻指调用 
    \textsc{InsertionSort}$(h^\prime)$之后，而不包括
    \textsc{InsertionSort}$(h^\prime)$的进行过程中)}:
    \[1\leqslant i\leqslant n − h, A[i]\leqslant A[i + h] \]
    实际上，我们只需要对任意步长$h_1$和$h_2$，证明连续调用
    \textsc{InsertionSort}$(h_2)$和\textsc{InsertionSort}$(h_1)$
    之后，$\forall i:A[i]\leqslant A[i + h_2]$；然后归纳得到结果\\
    1. 对任意的$h_1$，$h_2$ 证明以上性质\\
    2. 对 Lecture 2 中 Shell Sort 部分的引理 1，利用课堂上的框架
    ，提供一个完整的严格证明.}
\end{exercise}

以下设数列$A[1\ldots n]$

1.\begin{proof}
    当对数列$A$进行\textsc{InsertionSort}($h_2$)后，可以将$A$按
如下进行排列
\[\begin{matrix}
    A[1]&A[1+h_2]&A[1+2h_2]&\cdots\\
    A[2]&A[2+h_2]&A[2+2h_2]&\cdots\\
    \vdots&\vdots&\vdots&\\
    A[i]&A[i+h_2]&A[i+2h_2]&\cdots\\
    \vdots&\vdots&\vdots&\\
    A[h_2]&A[2h_2]&A[3h_2]&\cdots\\
\end{matrix}\]
该排列中每一行都符合从左到右依次递增，而此后进行
\textsc{InsertionSort}($h_1$)时，是对如下的排列
\[\begin{matrix}
    A[1]&A[1+h_1]&A[1+2h_1]&\cdots\\
    A[2]&A[2+h_1]&A[2+2h_1]&\cdots\\
    \vdots&\vdots&\vdots&\\
    A[i]&A[i+h_1]&A[i+2h_1]&\cdots\\
    \vdots&\vdots&\vdots&\\
    A[h_1]&A[2h_1]&A[3h_1]&\cdots\\
\end{matrix}\]
中的每一行进行从左到右排序，且每一行的排序互不影响，得到如下新排列
\[\begin{matrix}
    A'[1]&A'[1+h_1]&A'[1+2h_1]&\cdots\\
    A'[2]&A'[2+h_1]&A'[2+2h_1]&\cdots\\
    \vdots&\vdots&\vdots&\\
    A'[i]&A'[i+h_1]&A'[i+2h_1]&\cdots\\
    \vdots&\vdots&\vdots&\\
    A'[h_1]&A'[2h_1]&A'[3h_1]&\cdots\\
\end{matrix}\]
其中任意一行对应两集合顺序不同
\[A'_i=\{A'[i],A'[i+h_1],\cdots,A'[i+k\cdot h_1]\}=\{A[i],A[i+h_1],\cdots,A[i+k\cdot h_1]\}=A_i\]
且$A'[i]\leqslant A'[i+h_1]\leqslant \cdots\leqslant A'[i+k\cdot h_1],\forall 1\leqslant i\leqslant h_1$
其中$k=\lfloor (n-i)/h_1\rfloor$.

对每个$A'_i$定义对应的排列
\[B_i=\{A'[i+h_2],A'[i+h_2+h_1],\cdots,A'[i+h_2+k'h_1]\}\]
其中$k'=\lfloor(n-i-h_2)/h_1\rfloor$，易知
$B_i\subseteq A'_{(i+h_2)\mod h_1}$，
此处的$\mod$修正为$n\cdot h_1\mod h_1=h_1,n\in\mathbb{Z}$.

显然，$B_i$内从左到右也是依次增大的，且对每个$y'_m=A'[i+h_2+m\cdot h_1]\in B_i,\forall 0\leqslant m\leqslant k'$
总存在一个$y_n=A[i+h_2+n\cdot h_1]\in A_{(i+h_2)\mod h_1},1\leqslant n\leqslant k$，有$y_n=y'_m$.

又由\textsc{InsertionSort}($h_2$)的执行结果，存在
$x_n=A[i+n\cdot h_1]\leqslant y_n$.由$x_n$下标的互不相同以及
\textsc{InsertionSort}($h_2$)的执行后$y'_m$的递增属性，得$y'_m$
大于等于$\{x_n\}$中前$m$小的所有值，也即
\[A'[i+n\cdot h_1]\leqslant y'_m,\forall 0\leqslant n\leqslant m\]
其中取$n=m$有$A'[i+m\cdot h_1]\leqslant A'[i+h_2+m\cdot h_1]$.由$i,m$选取的任意性，原命题成立.
\end{proof}

2.\begin{proof}
     $H=\{h_t=2^t-1,t=\lfloor\log n\rfloor,\ldots,1\}$，则有$h_{t+1}$和$h_t$互质.
由命题1在执行过\textsc{InsertionSort}($h_{t+1}$)和
\textsc{InsertionSort}($h_t$)之后，数列分别以$h_{t+1}$和$h_t$为
步长递增，则$\forall a,b\in\mathbb{N}$，数列也是以$a\cdot h_{t+1}+b\cdot h_t$
为步长递增的.

$\forall j>h_{t+1}\cdot h_t,\forall l<j-h_{t+1}\cdot h_t,j-l>h_{t+1}\cdot h_t$，
不妨设$j-l=h_{t+1}\cdot h_t+p=(2^{t+1}-1)\cdot (2^t-1)+p,p>0$，
同时设$p=k\cdot (2^t-1)+q=k\cdot h_t+q,k\in\mathbb{N},0\leqslant q<h_t$，
取$a=q\geqslant0,b=2^{t+1}+k-1-2q>2^{t+1}-1-2(2^t-1)=1$，则$a,b\in\mathbb{N}$有
\[j-l=(2^{t+1}-1)\cdot (2^t-1)+k\cdot (2^t-1)+q=q\cdot(2^{t+1}-1)+(2^{t+1}+k-1-2q)\cdot(2^t-1)=a\cdot h_{t+1}+b\cdot h_t\]

因此，对执行过\textsc{InsertionSort}($h_{t+1}$)和
\textsc{InsertionSort}($h_t$)之后的数列执行\textsc{InsertionSort}($h_{t-1}$)时，
每一个数都只需在其之前$h_{t+1}\cdot h_t$的范围内以$h_{t-1}$为步长
进行移动，时间复杂度$O(\frac{h_{t+1}\cdot h_t}{h_{t-1}})$.因此对
整个数组，时间复杂度就是 \[O\left(\frac{n\cdot h_{t+1}\cdot h_t}{h_{t-1}}\right)\]

\end{proof}
\end{document}
