\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月15日}

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

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

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{automata, positioning, arrows}

\newcounter{aufgc}
\newenvironment{example}[1]%
{\refstepcounter{aufgc}\textbf{例题1.\arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

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

\lstset{basicstyle=\ttfamily}

\begin{document}

已知归并排序和快速排序的时间复杂度为$O(n\log n)$，那么是否存在更快的
时间复杂度？同时因为读数的时间复杂度为$\Omega(n)$，所以有可能的最快
排序算法为$O(n)$.

实际上，我们有所有基于比较的排序算法时间复杂度有下界$\Omega(n\log n)$，
因为这些算法对于任何数据结构都可以实现，所以无法做到$O(n)$.

但对于有上界的整数，存在线性时间排序算法.

\section*{比较排序}

\begin{definition}
    比较排序：基于两个元素的比较得到输出顺序的排序
\end{definition}



\begin{theorem}
    所有比较排序的时间复杂度多于$0.1n\log n$.
\end{theorem}

我们有如下的观察，所有的比较排序，运行时间都比比较的次数要多.

则以上定理，即所有比较排序的比较次数总多于$0.1 n\log n$，以下证明一
种特例，即那些有确定性且总能得到正确的结果的排序算法.

\begin{proof}
    考虑任一种排序算法\verb|CSort|，固定$n$，取$A=$permutation of 
    $\{1,2,\ldots,n\}$，只需证存在一种乱序，使得\verb|CSort|需要花
    $0.1n\log n$次排序去输出正确的结果.

    引入判定树的概念，将每次排序的开始作为树根，每个叶节点为正确输出
    终止，每个节点对应一次比较，每条边对应$\leqslant$或$>$.

    因此，比较排序的最差时间对应从树根到树叶最深的深度，即证该深度对
    应$n\log n$.

    判定树有$n!$个置换对应的树叶，即深度至少为$\log_2(n!)$，利用
    Stirling公式，可得到即为$\Omega(n\log n)$.
\end{proof}

有以下一些扩展：均摊时间复杂度为$\Omega(n\log n)$，随机比较排序算法
的时间复杂度期望也一样.

\section*{计数排序}

一种针对特殊数列的排序算法是计数排序.

考虑所有的元素都在$[0,1,\ldots,k]$，其中$k=O(n)$.不使用比较，直接
统计数列中等于$i$的个数$c_i$，那么所有值为$i$的元素排序后都应位于
$\sum_{j=0}^{i-1}c_j+1$到$\sum_{j=0}^{i}c_j$之间.因此得到如下算法.

\begin{algorithm}
    \caption{\textsc{Counting-Sort} $(A,B,k)$}
    let $C[0..k]$ be a new array\\ 
    \For{$i=0$ \KwTo $k$}{$C[i]=0$}
    \For{$j=0$ \KwTo $A.length$}{$C[A[j]]=C[A[j]]+1$}
    \tcp{$C[i]$ now contains the number of elements equal to $i$.}
    \For{$i=1$ \KwTo $k$}{$C[i]=C[i]+C[i-1]$}
    \tcp{$C[i]$ now contains the number of elements less than or equal to $i$.}
    \For{$j=A.length$ \KwTo $0$}{
        $B[C[A[j]]]=A[j]$\\
        $C[A[j]]=C[A[j]]-1$
    }
\end{algorithm}

算法满足稳定性：对于有着相同值的输入，输出的顺序与输入是一致的.
由于最后是逆序输出，则该性质是显然的.

该算法的时间复杂度为$O(n+k)$，为线性时间复杂度.

那么如果$k$很大时如何处理呢？比如$k=n^{O(1)},k=2^{64}$.

\section*{基数排序}

当$k$很大时，考虑所有数的二进制的表示.一种很容易想到的方法是从二进制
最高位到最低位依次分组按$0,1$分类，但这样需要存储$\log_2k$组，比较复
杂.

一种同样很简单的排序算法是基数排序，如下.

\begin{algorithm}
    \caption{\textsc{Radix-Sort} $(d)$}

    \For{$i=1$ \KwTo}{
        use a stable sort (e.g. \textsc{CountingSort}) to sort array A on digit $i$
    }
\end{algorithm}

同样其正确性依据stable稳定性是显然的.
时间复杂度为$O(d(n+k))$，其中$d$为位数，可以调整$d,k$使时间复杂度最
优.假设$b=\log_2(\max A[i])$，可以让$k=2^r$，有$O(\frac{b}{r}\cdot (n+2^r))$，
取$r=\Theta(\log n)$，有$O(\frac{b}{\log n}\cdot n)$；当$b=O(\log n)$，
即$A$中所有数在$poly(n)$内，则有$O(n)$，是线性时间复杂度的.

\section*{分治算法}

分拆，处理，合并

将规模为$n$的问题拆分成$a$个大小为$\lceil n/b\rceil$的子问题，每个
子问题的处理时间为$T(\cdot)$，合并的时间为$f(n)$，总的时间复杂度为
\[T(n)=a\cdot T(\lceil n/b\rceil)+f(n)\]

要计算$T$的大小由以下三种算法：替代，

\end{document}
