ch1ch2.tex

\documentclass{article}
\XeTeXlinebreaklocale "zh"
\XeTeXlinebreakskip = 0pt plus 1pt minus 0.1pt
\usepackage{float}
\usepackage{fontspec}
\usepackage{amssymb}
\setmainfont{Times New Roman}
\usepackage{indentfirst}
\usepackage{zhspacing}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath}
\zhspacing
\usepackage[english]{babel}

%% 提供《算法导论》口味的算法排版，详见clrscode.pdf
\usepackage{clrscode}
%% 提供floor和ceiling
\usepackage{mathtools}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}


\begin{document}

\section{写出求整数最大公因子的欧几里得算法}
\large {
\begin{codebox}
  \Procname{$\proc{Euclid}(a, b)$}
  \li \If $b = 0$
  \li  \Then  \Return $a$
  \li \ElseNoIf \Return $\proc{Euclid}(b, a\  \text{mod}\  b)$
      \End
\end{codebox}
}

\section{证明或否证：$f(n)+o(f(n))=\Theta(f(n))$}

\section{试证明：$O(f(x))+O(g(x))=O(max(f(x), g(x)))$}

\section{证明或给出反例：$\Theta(f(n)) \cap o(f(n)) = \emptyset $}

\section{证明：设$k$是任意常数正整数，则$\log^kn=o(n)$}

\section{用迭代法解方程$T(n)=T(9n/10)+n$}

\section{解方程$T(n)=6T(n/3)+\log n$}

\section{解方程$T(n)=3T(n/3+5)+n/2$}

\section{解方程$T(n)=T(\ceil {n/2})+1$}

\section{解方程$T(n)=9T(n/3)+n$}

\section{解方程$T(n)=T(\floor {n/2})+n^3$}

\section{解方程$T(n)=2T(\sqrt[4]n)+(\log_2n)^2$}


\section{解方程}
\large {
  $
  T(n) \leq \begin{cases}
    C_1 & n < 20\\
    C_2n+4T(n/5) & n \geq 20\\
  \end{cases}
  $
}

\end{document}