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

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

\section*{傅里叶变换}

范德蒙德矩阵：$\omega=e^{2\pi i/N},\omega^N-1=0$，$N=2^n$，$V_N={(\omega^{i\cdot j})}_{ij}$其中$i,j=0,1,\ldots,N-1$

傅里叶变换可以在$O(n\log n)$时间复杂度内计算矩阵和向量的乘法，在$O(n^2\log n)$时间复杂度内计算矩阵和矩阵的乘法

\begin{theorem}
    \[V_N^{-1}=\frac{1}{N}\overline{V_N}\]
\end{theorem}

\begin{proof}
    利用$\omega_N^0,\ldots,\omega_N^{N-1}$的对称性，有$\sum_j\omega_N^{j\cdot k}=0,k=1,\ldots,N-1$，$k=0$时该求和为0

    因此有$\overline{V_N}\cdot V_N=N\cdot I$
\end{proof}

\begin{definition}
    卷积：两个向量${\boldsymbol\alpha}=({\boldsymbol\alpha}[0],\ldots,{\boldsymbol\alpha}[N-1])$，${\boldsymbol\beta}=({\boldsymbol\beta}[0],\ldots,{\boldsymbol\beta}[N-1])$，则他们的卷积为
    \[({\boldsymbol\alpha}*{\boldsymbol\beta})[k]=\sum_{l=0}^{N-1}{\boldsymbol\alpha}[l]\cdot{\boldsymbol\beta}[(k-l)\mod N]\]
\end{definition}

有以下性质：$V_N(\boldsymbol{\alpha}*\boldsymbol{\beta})=(V_N\boldsymbol{\alpha})\cdot(V_N\boldsymbol{\beta})$，其中$\cdot :=(\boldsymbol{v}\cdot \boldsymbol{u})[i]=\boldsymbol{v}[i]\boldsymbol{u}[i]$

\section*{最近邻搜索}

给定$n$个点和点的距离，求最近的一对，不加处理，该问题需要$\Omega(n^2)$的时间复杂度。

为了简化问题，给定平面$\mathbb{R}^2$上的$n$个点，求最小欧几里得距离

\begin{theorem}
    分治算法可以在$O(n\log n)$时间复杂度内解决该问题
\end{theorem}

显然最明显的解决方法需要$O(n^2)$，为了简化，我们假设没有点的横纵坐标相同.

一种$O(n^2\log n)$的算法是画一条线，将点分成两部分，分别求最近点对，再考虑上线两侧的点对，最后求出最小值.

其中的难点在于怎样求交叉点对，令$\delta$为子问题的最近距离，则不需要考虑所有的交叉点对，只需考虑在线两侧$\delta$距离内的点对，即一个$2\delta$宽的长条，问题则转变为求这一长条内有多少交叉点对.

将该长条划分为一个个$\delta/2\times\delta/2$的方格，我们认为同一个$\delta/2\times\delta/2$的方格中最多有一个点，否则因为一个方格都在线的一边，则存在距离$\sqrt{2}\delta/2$，与$\delta$为子问题最小距离矛盾.

而每个方格在$\delta$距离内的方格最多有8个，所以对每个点最多只需考虑常数个点，

如果每次都进行排序，则需要$T(n)=2T(n/2)+n\log n$，计算可得$T(n)=O(n\log^2 n)$.

进行优化的话，可以考虑使用MergeSort，或是在最初的时候排序好，之后都无需排序，这样可以得到$O(n\log n)$的时间复杂度.

\section*{二分查找}

算法比较显然，略.

扩展：在$O(\log n)$时间复杂度内计算$a^n$，快速幂.

快速幂扩展：在$O(\log n)$时间复杂度内计算斐波那契数列，矩阵快速幂.

\[\left(\begin{matrix}
    F_{n+1} \\
    F_n
\end{matrix}\right)=\underbrace{\left(\begin{matrix}
    1 & 1 \\
    1 & 0
\end{matrix}\right)}_{A}\left(\begin{matrix}
    F_{n} \\
    F_{n-1}
\end{matrix}\right)s.t.\left(\begin{matrix}
    F_{n+1} \\
    F_n
\end{matrix}\right)=A^n\left(\begin{matrix}
    F_{1} \\
    F_{0}
\end{matrix}\right)
\]

\section*{时间复杂度总结}

$T(n)=T(n/2)+O(1)$

$T(n)=2T(n/2)+O(n)$

$T(n)=7T(n/2)+O(n^2)$



\end{document}
