《算法导论》第4章部分题解

4月5日 · 2018年

《算法导论》第4章部分题解

练习题4-5.2

首先看Strassen算法
$$
T(n)=7T(\frac{n}{2})+\Theta(n^2)
$$
这里,有
$$
\begin{align}
a&=7\\
b&=2\\
f(n)&=\Theta(n^2) \\
\end{align}
$$
因此
$$
n^{\log_{b}{a}}=n^{\log_{2}{7}}
$$
将$$log_{2}{7}$$改写为$$\lg7$$

由于$$2.80\lt\lg7\lt2.81$$

知道对于$$\epsilon=0.8$$有
$$
f(n)=O(n^{\lg{7}-\epsilon})
$$
最终得到解
$$
T(n)=\Theta(n^{\lg{7}})
$$
然后考虑Caesar教授的递归式
$$
T(n)=aT(\frac{n}{4})+\Theta(n^2)
$$
这里,有
$$
\begin{align}
b&=4\\
f(n)&=\Theta(n^2) \\
\end{align}
$$

类似的,由主定理,可以得到解
$$
T(n)=\Theta(n^{log_{4}{a}})
$$
如果要击败Strassen算法,显然要
$$
\log_{4}{a} \lt \log_{2}{7}
$$

$$
\begin{align}
\log_4{a}&\lt \log_2{7} \\
\frac{1}{2} \log_2{a} &\lt \log_2{7} \\
\log_2{a} &\lt \log_2{49} \\
a &\lt 49 \\
由对数定义,a &\gt 0 \\
于是 0 \lt &a \lt 49
\end{align}
$$

从题目的实际意义,知道a应该是一个正整数

那么,a的最大整数值应该是48

思考题4-6

a

首先证明必要性

根据定义
$$
\forall i,j,k,l,有A[i,j]+A[k,l] \le A[i,l]+A[k,j]成立
$$
那么此矩阵为Monge阵列

所以,一个矩阵为Monge阵列,必定有
$$
A[i,j]+A[k,l] \le A[i,l]+A[k,j]对\forall i,j,k,l成立
$$
取$$k=i+1$$,取$$l=j+1$$,则有
$$
A[i,j]+A[i+1,j+1] \le A[i,j+1]+A[i+1,j]
$$
对所有$$i=1, 2, …, m-1$$和$$j=1, 2, …, n-1$$成立

接着证明充分性
$$
\begin{align}
A[i,j]+A[i+1,j+1] \le A[i,j+1]+A[i+1,j] \\
\Rightarrow A[i,j]-A[i,j+1] \le A[i+1,j]-A[i+1,j+1] \\
\end{align}
$$
对行号i用归纳法

$$
\left\{
\begin{align}
&A[i,j]-A[i,j+1] \le A[i+1,j]-A[i+1,j+1] \\
&A[i+1,j]-A[i+1,j+1] \le A[i+2,j]-A[i+2,j+1] \\
&\cdots \\
&A[m-1,j]-A[m-1,j+1] \le A[m,j]-A[m,j+1] \\
\end{align}
\right.
$$
于是
$$
A[i,j]-A[i,j+1] \le A[i+1,j]-A[i+1,j+1] \le \cdots \le A[m,j]-A[m,j+1]
$$
对于给定的j,都有
$$
\forall k, i\lt k \le m, A[i,j]-A[i,j+1] \le A[k,j]-A[k,j+1]
$$

$$
\forall k, 1\le i\lt k \le m, A[i,j]+A[k,j+1] \le A[i,j+1]+A[k,j]
$$
同理,对列号j用归纳法,对于给定的i,都有
$$
\forall l, 1\le j\lt l \le n, A[i,j]+A[i+1,l] \le A[i,l]+A[i+1,j]
$$
综上,不等式两边同时加和,对于同时给定的i, j


$$
\forall k,l, 1\le i\lt k \le m, 1\le j\lt l \le n, A[i,j]+A[k,l] \le A[i,l]+A[k,j]
$$
该不等式与定义一致

所以这是Monge阵列

b

由上题的充分必要性,不需要检查每任意两行两列,只要检查i行、i+1行、j列、j+1列即可
$$
\begin{equation}
{
\left[ \begin{array}{cccc}
37 & 23 & 22 & 32\\
21 & 6 & 7 & 10\\
53 & 34 & 30 & 31\\
32 & 13 & 9 & 6\\
43 & 21 & 15 & 8\\
\end{array}
\right]
}
\end{equation}
$$
考察$$37+6\le 21+23$$成立

考察$$21+34\le 53+6$$成立

考察$$53+13 \le 32+34$$成立

……

考察$$23+7>6+22$$不成立

所以需要修改23或7使这两个数变小,或者修改6或22使这两个数变大

但是需要注意的是,修改其中一个数,需要保证不影响其他的行和列

不妨修改第2行第3列的7

由上题的充分必要性,只要检查

  • 第1行、第2行、第2列、第3列
  • 第1行、第2行、第3列、第4列
  • 第2行、第3行、第2列、第3列
  • 第2行、第3行、第3列、第4列

即可

于是,可能受到影响的为
$$
\begin{equation}
{
\left[ \begin{array}{cc}
23 & 22\\
6 & 7 \\
\end{array}
\right]
},
{
\left[ \begin{array}{cc}
22 & 32\\
7 & 10 \\
\end{array}
\right]
},
{
\left[ \begin{array}{cc}
6 & 7\\
34 & 30 \\
\end{array}
\right]
},
{
\left[ \begin{array}{cc}
7 & 10\\
30 & 31 \\
\end{array}
\right]
}
\end{equation}
$$
只要这些小矩阵满足左上和右下角的和小于左下和右上角的和,由上题充分必要性,整个矩阵为Monge阵列

答案不唯一,例如,把7修改为4,即满足,所以,把第2行第3列的7修改为4

c

反证法

假设存在a、b满足$$a\lt b$$,且$$f(a) \gt f(b)$$

意味着第a行最左最小的元素的列下标(记为c),大于第b行最左最小元素的下标(记为d)

取a行、b行、c列、d列

考察
$$
\begin{equation}
{
\left[ \begin{array}{cc}
A_{a,d} & A_{a,c}\\
A_{b,d} & A_{b,c} \\
\end{array}
\right]
}
\end{equation}
$$
$$A_{a,c}$$是a行最左最小的元素,所以,$$A_{a,d} \gt A_{a,c}$$

同样的,有$$A_{b,c} \gt A_{b,d}$$

于是
$$
A_{a,c}+A_{b,d} \lt A_{a,d}+A_{b,c}
$$
左下和右上的元素之和,小于左上和右下的元素和

这与A矩阵是Monge阵列矛盾

所以假设不成立

原命题得证

d

不失一般性,假设第2行的最左最小元素的列下标为a,即
$$
f(2)=a
$$
那么,第1行的最左最小元素的列下标一定小于等于a,即
$$
1\le f(1)\le a
$$
同样的,设$$f(4)=b$$,那么有
$$
a \le f(3)\le b
$$
如此,只要遍历
$$
1\to a,a\to b, \cdots
$$
就可以求出奇数行的最左最小元素的列下标

最坏的情况,这里求奇数行的最左最小元素的列下标过程,当求出所有奇数行的时候,会遍历完整个所有的列数n

同时,由于上面的遍历中,偶数行的值a、b等被比较了2次

偶数行一共m行,每一行的最左最小值被遍历了2次

其中一次可以认为正好是算在了列数那里,那么另外一次就是多余的要比较的

所以,最终遍历的次数就是列数m加上行数n的二分之一


$$
n+\frac{m}{2}
$$
由此
$$
O(n+m)
$$

e

偶数行的最左最小元素下标是分治得到的,所以有
$$
T(m)=T(\frac{m}{2})+f(x)
$$
由上题答案知道,在偶数行最左最小值已知的情况下,能在$$O(m+n)$$时间内计算出奇数行的最左最小值

所以
$$
T(m)=T(\frac{m}{2})+O(m+n)
$$

由主定理,有
$$
O(m+nlogm)
$$

编写程序实现Monge矩阵相关的题目

判断Monge矩阵

判断一个矩阵是不是Monge阵列,方法有二

第一是按照定义,但是显然比较麻烦

所以采用第二种方法,即上题(a)中的充分必要性结论

那么,充分必要性结论
$$
\forall i,j, 1\le i \le m-1, 1 \le j \le n-1 \
A[i,j]+A[i+1,j+1] \le A[i,j+1]+A[i+1,j]
$$
可以得到如下代码

输入输出部分从略

/**
 * 判断一个矩阵是不是Monge阵列
 * @return 如果是Monge阵列,返回true,否则,false
 */
private static boolean isMonge() {
    for (int i = 0; i < matrix.length - 1; ++i)
        for (int j = 0; j < matrix[i].length - 1; ++j)
            if (matrix[i][j] + matrix[i + 1][j + 1] > matrix[i + 1][j] + matrix[i][j + 1])
                return false;
    return true;
}

给出详细的算法设计思想,并分析算法运行时间

算法思想已经在上面讲的很清楚了

这里分析运行时间

从上面的代码可以看出

双重循环

$$(n-1) \times (m-1)$$

所以复杂度是
$$
O(mn)
$$
事实上,考虑输入输出

规模为$$m\cdot n$$的矩阵,复杂度也是$$O(mn)$$

0 条回应
验证码
输入运算符及数字使等式成立
{{comment.validate_num1}} = {{comment.validate_num2}}
点赞确定
退出登录?
取消 确定