\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[hidelinks]{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}

\setlength{\headheight}{0pt}
\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年11月22日}

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

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

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{arrows, positioning}

\newcounter{aufgc}
\newenvironment{exercise}[1]%
{\refstepcounter{aufgc}\textbf{问题 \arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

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

\definecolor{mygray}{rgb}{0.4,0.4,0.4}
\definecolor{mygreen}{rgb}{0,0.8,0.6}
\definecolor{myorange}{rgb}{1.0,0.4,0}

\lstset{
    basicstyle=\footnotesize\sffamily\color{black},
    basicstyle=\tt,
    keywordstyle=\color{purple}\bfseries,
    commentstyle=\color{mygray},
    numbers=left,
    numbersep=5pt,
    numberstyle=\tiny\color{mygray},
    showspaces=false,
    showstringspaces=false,
    stringstyle=\color{myorange},
    tabsize=2,
    backgroundcolor=\color[RGB]{245,245,244}
}

\begin{document}

\textbf{Q1.}

首先去除那些重量比 $W$ 大的物品，然后对所有的剩余物品，对它们的重量作变换 $\tilde{w}_i=\lfloor \frac{w_i}{b}\rfloor b$，
其中取 $b=\frac{\varepsilon W}{n}$，而只需对所有剩余物品，因为都乘
相同系数 $b$，此时同时除去，因此只需按重量
$\hat{w_i}=\lfloor \frac{w_i}{b}\rfloor$，价值 $v_i$，来用动态规划即可，时间复杂度为 $O(n\hat{W})$，
而 $\hat{W}=\lfloor \frac{W}{b}\rfloor=\lfloor\frac{n}{\varepsilon}\rfloor$，
因此时间复杂度为 $O(\frac{n^2}{\varepsilon})$，是多项式时间算法.

而因为算法中只可能把物品的重量降低了，因此原本的最优解依然满足，算法
得到的结果不会弱于原本的最优解 $V$.而每个物品在算法中最多被考虑成比实际
轻 $b$，因此最坏情况下，得到的总重量为 $W+nb=W+\varepsilon W=(1+\varepsilon)W$.

\hrulefill\medskip

\textbf{Q2.}

\begin{algorithm}
    \caption{二分查找}
    \KwIn{数组 $A$，数组长度 $n$}
    \KwOut{目标的下标 $i$}

    $l\leftarrow 1$，$r\leftarrow n$\;
    \While{$l\leqslant r$}{
        $m\leftarrow \lfloor \frac{l+r}{2}\rfloor$\;
        \If{$A[m]\neq A[m+1]$}{
            \Return{$m$}\;
        }
        \ElseIf{$A[m]\neq A[n]$}{
            $l\leftarrow m+1$\;
        }
        \Else{
            $r\leftarrow m-1$\;
        }
    }
\end{algorithm}

时间复杂度为 $O(\log n)$，因为每次将原本的数组切成两半，之后只考虑
其中一半的部分.

\hrulefill\medskip

\textbf{Q3.}

\begin{algorithm}[ht]
    \caption{求解 $\bar{H}_n v$}\label{algo:Hv}
    \KwIn{矩阵 $\bar{H}_n$，向量 $v$，参数 $n$}
    \KwOut{向量 $\bar{H}_n v$}
    $v_1\leftarrow v[1:2^{n-1}],v_2\leftarrow v[2^{n-1}+1:2^n]$\;
    $v_1\leftarrow$ 求解 $\bar{H}_{n-1} v_1$\;
    $v_2\leftarrow$ 求解 $\bar{H}_{n-1} v_2$\;
    \Return{$[v_1+v_2,v_1-v_2]$}\;
\end{algorithm}

见算法~\ref{algo:Hv}，有 $T(n)=2T(n-1)+O(2^{n-1})$，要证明 $T(n)=O(n\cdot 2^n)$，
只需有 $T(n)\leqslant c\cdot n2^n$，假设 $O(2^{n-1})$ 系数为 $d$，
则只需 \[T(n)\leqslant 2c(n-1)2^{n-1}+d\cdot2^{n-1}=c\cdot n2^n-(2c-d)2^{n-1}\leqslant c\cdot n2^n\]
因此只需满足 $2c\geqslant d$，即有 $T(n)=O(n2^n)$，而这是可以满足的，因此可以判断算法时间复杂度为 $O(n2^n)$.

\newpage

\textbf{Q4.}

(a)

\begin{proof}
    考虑最极端的情况，假设一次询问时所有同学的权重和为 $W$，其中选择
    了错误答案的同学权重和恰好为 $\frac{W}{2}+\varepsilon$ ($\varepsilon$ 极小)，
    则之后更新权重和为 $\frac{3W}{4}$.

    对小牛帮助最大同学判断 $m$ 次错误之后，权重变为 ${(\frac{1}{2})}^m$，
    只需要让这个值超过权重和的一半，就能保证小牛不会再判断错误.

    假设小牛判断错误 $t$ 次后不会再判断错误，则有
    \[{\left(\frac{1}{2}\right)}^m>{\left(\frac{3}{4}\right)}^t\cdot n\cdot\frac{1}{2}\]
    解得 $t>\frac{m-1+\log_{2}n}{2-\log_{2}3}$，因此小牛至多判断
    错误 $\frac{1}{2-\log_{2}3}(m+\log_{2}n)$ 次.
\end{proof}

(b)

\begin{proof}
    假设第 $i(i=1,2,\ldots)$ 次询问时所有同学权重和为 $W_i$，其中选择
    了错误答案的同学权重和为 $a_i W_i(0\leqslant a_i\leqslant 1)$，
    则之后权重和更新为 $W_i(1-a_i+\beta a_i)=W_i[1+(\beta-1)a_i]$.

    因此，经过 $t$ 次询问，总的权重和更新为 $n\cdot\prod_{i=1}^{t}[1+(\beta-1)a_i]$，
    对小牛帮助最大同学判断 $m$ 次错误之后，权重变为 $\beta^m$.显然，应该有
    \[n\cdot\prod_{i=1}^{t}[1+(\beta-1)a_i]\geqslant\beta^m\]
    同时取对数，有
    \[\ln n+\sum_{i=1}^{t}\ln[1+(\beta-1)a_i]\geqslant m\ln\beta\]
    对于 $\sum_{i=1}^{t}\ln[1+(\beta-1)a_i]$，考虑琴生不等式，有
    \[\sum_{i=1}^{t}\ln[1+(\beta-1)a_i]\leqslant t\ln[1+\frac{\sum_{i=1}^{t}(\beta-1)a_i}{t}]\leqslant t\ln\beta\leqslant t(\beta-1)\]
    因为 $\beta-1<0$，有 \[t\leqslant\frac{m\ln\beta-\ln n}{\beta-1}=\frac{m\ln\frac{1}{\beta}+\ln n}{1-\beta}\]
    因此判断错误期望次数最多为 $\frac{m\ln\frac{1}{\beta}+\ln n}{1-\beta}$.
\end{proof}

\end{document}