\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\documentclass[12pt,a4paper]{article}
\usepackage{geometry}
\geometry{left=2.5cm,right=2.5cm,top=2.0cm,bottom=2.5cm}
\usepackage[english]{babel}
\usepackage{amsmath,amsthm}
\usepackage{amsfonts}
\usepackage[longend,ruled,linesnumbered]{algorithm2e}
\usepackage{fancyhdr}
\usepackage{ctex}
\usepackage{array}
\usepackage{listings}
\usepackage{color}
\usepackage{graphicx}
\begin{document}
\title{
{\heiti《算法分析与设计》第 {$2$} 次作业
\footnote{
%要求：1、分析题请用书面化语言给出详细分析过程;~2、实现题请先写出算法思想，其次用伪代码描述，C++源码可以采用在线提交的方式，提交密码：seu711181，用户名最好统一使用学号-姓名的格式。
}
}
}
\date{}
\author{
姓名：\underline{你的名字}~~~~~~
学号：\underline{你的学号}~~~~~~}
\maketitle
\noindent
\section*{\heiti \color{red}{算法分析题}}
\noindent
{\bf 题目1：}求下列递推关系表示的算法复杂度
\begin{enumerate}
\item[(1)] $T(n)$ = 9$T(n/3)$ + $n$
\item[(2)] $T(n)$ = $n$ + $3T(\frac{n}{4})$
\item[(3)] $T(n)$ = $4T(n/2)$ + $n^2\lg{n}$
\end{enumerate}
\vspace{5pt}
\noindent
{\bf 答：}
\vspace{10pt}
\noindent
{\bf 题目2：}假设谷歌公司在过去$n$天中的股票价格记录在数组$A[1..n]$中，我们希望从中找出两天的价格，其价格增幅最大，即找到$A$[$i$]和$A$[$j$] $(i\leq j)$ 使得$M=A[j]-A[i]$的值最大，请设计一个时间复杂度不超过$O(n\lg{n}$)的分治算法
\vspace{5pt}
\noindent
{\bf 答：}
\noindent
\section*{\heiti \color{red}{算法实现题}}
\vspace{10pt}
\noindent
{\bf 题目3：}问题描述：在与联盟的战斗中连续失败后，帝国撤退到最后一个据点。根据其强大的防御系统，帝国击退了联盟攻击的六波浪潮。经过几个不眠之夜，联盟将军亚瑟注意到防御系统的唯一弱点就是能源供应。该系统由N个核电站供电，其中任何一个都会使系统失效。
这位将军很快就派N名特工进行突击，这些特工进入了据点。不幸的是，由于帝国空军的袭击，他们未能降落在预期位置。作为一名经验丰富的将军，亚瑟很快意识到他需要重新安排计划。他现在要知道的第一件事是哪个特工离任何一个核电站最近。你是否可以帮助将军计算特工与核电站之间的最小距离？
%题目细节及提交地址：https://vjudge.net/contest/359940
\vspace{5pt}
\noindent
{\bf 答：}
\end{document}\