-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathHomework06-1.tex
211 lines (187 loc) · 9.58 KB
/
Homework06-1.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
\section{0323}\label{sec:0323}
\begin{questions}
\question 设计算法将$1$到$n^2$按顺时针方向由内而外填入一个$n \times n$的矩阵
例如$n=2$时，$
\begin{array}{cc}
2 & 3 \\
1 & 4
\end{array}
$；$n=5$时，$
\begin{array}{ccccc}
25 & 10 & 11 & 12 & 13 \\
24 & 9 & 2 & 3 & 14 \\
23 & 8 & 1 & 4 & 15 \\
22 & 7 & 6 & 5 & 16 \\
21 & 20 & 19 & 18 & 17
\end{array}
$
\begin{solution}
记该矩阵为$A[1..n][1..n]$。
当$n$为奇数时，去掉第一列和最后一行后，剩余的元素为$n-1$维的方阵；
当$n$为偶数时，去掉第一行和最后一列后，剩余的元素为$n-1$维的方阵。
\textbf{伪代码见算法\ref{0323:spiralmat}}
\end{solution}
\begin{algorithm}[!htp]
\caption{螺旋方阵}\label{0323:spiralmat}
\begin{algorithmic}[1]
\Require {
空间$A[1..n][1..n]$
}
% \Procedure{Main}{}
\State \Call{SpiralMatrix}{$A, 0, 0, n$}
% \EndProcedure
\Statex
\Procedure{SpiralMatrix}{$M, top, left, size$}
\Statex
\Comment{向以$M[top][left]$为$A[0][0]$的$size$维方阵中填入元素}
\If{$n=1$}
\State $M[top][left] \gets 1$
\ElsIf {$[n \bmod 2] = 1$} \Comment{去掉第一列和最后一行后，剩余的元素为$n-1$维的方阵}
\State \Call{SpiralMatrix}{$A, top, left+1, n-1$} \Comment{以左上角右侧的元素为基准}
\For {$i \gets 1$ to $n$}
\State $M[n][i] \gets (n-1)^2 + n - (i - 1)$ \Comment{填充下边}
\State $M[i][1] \gets n^2 - (i - 1)$ \Comment{填充左边}
\EndFor
\Else \Comment{去掉第一行和最后一行后，剩余的元素为$n-1$维的方阵}
\State \Call{SpiralMatrix}{$A, top+1, left, n-1$} \Comment{以左上角下侧的元素为基准}
\For {$i \gets 1$ to $n$}
\State $M[1][i] \gets (n-1)^2 + i$ \Comment{填充上边}
\State $M[i][n] \gets (n-1)^2 + n + (i - 1)$ \Comment{填充右边}
\EndFor
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}
\question 给定整数数组$A[1..n]$，相邻两个元素的值最多相差$1$。
设$A[1]=x$，$A[n]=y$，并且$x<y$，输入$z$，$x \leq z \leq y$，判断$z$在数组$A$中出现的位置。
给出算法及时间复杂性（不得穷举）
\begin{solution}
相邻两个元素的值最多相差$1$，即有$A[i+1] - A[i] \in \left\{-1, 0, 1\right\}$。
可以据此类比连续函数上的零点存在性定理，即
\begin{center}
若$A[i] \leq z \leq A[j]$且$i < j$，则一定存在一个$m : i \leq m \leq j$使得$A[m] = z$
\end{center}
因此可用二分法，有算法\ref{0323:02}。该算法的时间复杂度为$O(\log n)$。
\end{solution}
\begin{algorithm}[!htp]
\caption{\quad}\label{0323:02}
\begin{algorithmic}[1]
\Require{整数数组$A[1..n]$, $A$中的一个整数$z$}
\Ensure{元素$z$在数组$A$中的位置}
\State $lidx \gets 1, ridx \gets n$
\State $mid \gets \left\lfloor \frac{lidx+ridx}{2} \right\rfloor$
\While{$A[mid] \neq z$}
\If {$A[mid] < z$}
\State $left \gets mid$ \Comment{更新后仍有$A[left] < z$}
\Else \Comment{$A[mid] > z$}
\State $right \gets mid$ \Comment{更新后仍有$A[right] > z$}
\EndIf
\State $mid \gets \left\lfloor \frac{lidx+ridx}{2} \right\rfloor$
\EndWhile
\State \Return $mid$
\end{algorithmic}
\end{algorithm}
\question 假设有$k$个长度为$n$的有序序列，采用下述方法将这些序列合并成一个具有$kn$个元素的有序序列：
将前两个序列合并，再并入第三个序列，然后是第四个……
直至所有序列合并。
\begin{parts}
\part 用$k$和$n$表示该方法的时间复杂性
\begin{solution}
当合并一个长度为$m$和一个长度为$n$的序列时\begin{itemize}
\item 赋值操作执行了$m+n$次
\item 比较操作至少执行$\min\left\{m,n\right\}$次，最多执行$2 \min\left\{m,n\right\}$次
\end{itemize}
所以此算法合并$k$个长度为$n$的有序序列所需时间为
\begin{align*}
T(0, k, n) = T(n, k-1, n) & = 2n + cn + T(2n, k-2, n) \\
& = (2+3)n + 2cn + T(3n, k-3, n) \\
& = \dots \\
& = \sum_{i=2}^{k} {i \cdot n} + (k-1)cn \\
& = \frac{(k+2)(k-1)}{2} n + (k-1)cn = O(k^2n)
\end{align*}
\end{solution}
\part 能不能得到一个效率更高的方法来合并这$k$个序列？
\begin{solution}
首先将第奇数个序列和第偶数个序列合并，形成$\left\lceil \frac{k}{2} \right\rceil$个最大长度为$2n$的序列；
然后重复上一步骤，直至最终只剩1个序列。
不妨设$k = 2^m$
\begin{align*}
T(k,n) & = \frac{k}{2} T(2,n) + T \left(\frac{k}{2}, 2n\right) = 2^{m-1} (2+c)n + T \left(2^{m-1} , 2n\right) \\
& = 2^{m-1} (2+c)n + 2^{m-2} 2(2+c)n + T \left(2^{m-2} , 4n\right) \\
& = 2 \cdot 2^{m-1} (2+c)n + T \left(2^{m-2} , 2^2 n\right) \\
& = \dots \\
& = (m-1) \cdot 2^{m-1} (2+c)n + T \left(2, 2^{m-1} n\right) \\
& = m \cdot 2^{m-1} (2+c)n = O(k n \log {k})
\end{align*}
\end{solution}
\end{parts}
\question 设$A[1..n]$是一个包含$n$个不同数的数组。
如果在$i<j$的情况下有$A[i]>A[j]$，则$(i,j)$为$A$中的一个逆序对。
\begin{parts}
\part 若$A=\left\{2, 3, 8, 6, 1\right\}$，列出其中所有的逆序对
\begin{solution}
\begin{center}
\begin{tabular}{c |ccccc}
\hline
index & 1 & 2 & 3 & 4 & 5 \\ \hline
value & 2 & 3 & 8 & 6 & 1 \\
\hline
\end{tabular}
\end{center}
\[ (1,5) \quad (2,5) \quad (3,4) \quad (3,5) \quad (4,5) \]
\end{solution}
\part 若数组元素取自$\left\{ 1, 2, \dots ,n \right\}$，那么怎样的数组含有最多的逆序对？它包含多少个逆序对？
\begin{solution}
当数组为递减序列时包含有最多的逆序对，此时序列中任取一对数，都能构成逆序对。
逆序对数为$\frac{n(n-1)}{2}$。
\end{solution}
\part 求任意数组$A$中逆序对的数目，并证明算法的时间复杂性为$\Theta(n \log{n})$
\begin{solution}
应用分治法，结合归并排序。
首先将数组等分成左右两个子序列，分别求出两边的逆序对数（并同时进行排序）。
然后再求出分属于两个子序列的逆序对，即对每一个左序列中的元素，找出右序列中大于该元素的所有元素个数。
\[ T(n) = 2T(n/2) + (2+c)n = O(n \log n) \]
\textbf{伪代码见算法\ref{0323:inversion}}
\end{solution}
\end{parts}
\begin{algorithm}[!htp]
\caption{求逆序对数}\label{0323:inversion}
\begin{algorithmic}[1]
\Require{数组$A[1..n]$}
\Ensure{$A$中的逆序对数$m$}
\State $(m, \_) \gets \Call{MergeInversions}{A[1..n]}$
\Statex
\Procedure{MergeInversions}{$A[1..n]$}
\Statex \Comment{输入一个数组$A$，输出一个二元组，包含该数组中的逆序对数及一个有序的该数组}
\If{$A.size = 1$}
\State \Return $(0, A)$
\ElsIf{$A.size = 2$}
\If{A[1] > A[2]}
\State \Return $(1, [A[2], A[1]])$
\Else
\State \Return $(0, A)$
\EndIf
\Else \Comment{分治}
\State $(nL, L) \gets \Call{MergeInversions}{A\left[1..\left\lfloor n/2 \right\rfloor\right]}$
\State $(nR, R) \gets \Call{MergeInversions}{A\left[\left\lfloor n/2 \right\rfloor+1 .. n\right]}$
\State $k \gets 1, cnt \gets 0$ \Comment{归并}
\While {$\neg L.empty \wedge \neg R.empty$}
\If{$ L.front \leq R.front $}
\State $A[k] = L.PopFront()$
\Else \Comment{$L[1]$大于$R$的所有剩余元素}
\State $A[k] = R.PopFront()$
\State $cnt \gets cnt + R.size$ \Comment{$L[1]$与$R$中所有剩余元素都构成逆序对}
\EndIf
\State $k \gets k + 1$
\EndWhile
\If{$\neg L.empty$} \Comment{填充剩余元素}
\State $A[k..n] = L$
\ElsIf{$\neg R.empty$}
\State $A[k..n] = R$
\EndIf
\State \Return $(cnt, A)$
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}
\end{questions}