Discrete mathematics and its applications 7th 第三章笔记
文章目录
算法及其复杂度分析
说明:笔记并不完整,只记录了书本的部分。
1.停机问题(The Halting Problem)
停机问题是 “证明存在不可解问题” 的一个例子
问题描述:
是否存在这样一个过程,该过程能以一个计算机程序以及该程序的一个输入作为输入,并判断在给定输入运行时是否最终停止。
原书证明(反证法):
最后与H所给的结果相违背是指和最开始H的定义相违背。
相似的题:
1.证明 判断一个程序在给定一个输入时总会输出数字“1”这个问题是不可解的。
证明:假设我有一个程序,它能够判断在给定一个输入时,是否输出数字“1”,那么我们就有办法解决停机问题(输入为程序P'及P'的输入I)。可以构造一个新的程序P,P和P'的原理一样,唯一不同的是,当P终止时,P'也会终止,但同时会输出数字“1”,然后我们把P'和I作为P的输入,这样就可以说明P在输入为P'和I的情况下判断是否终止,这与停机问题不可解相矛盾。
2.证明:“给定两个程序以及它们的输入,并且已知其中恰有一个会终止,判断哪一个程序会终止”这个问题是可解的。
证明:运行这两个程序,输入为上面的输入,看哪个程序会终止。进而判断这个程序会终止。(因为题目说恰有一个会终止)
3.证明判定一个特定程序给定特定输入时是否会停机的问题是可解的。
证明:因为是特定的程序和输入,运行判断是否终止,是就说明会停机,否则就说明不会停机。(因为这里指明了是特定输入,哪怕运行了10亿年才停止,这也是属于会停机,所以在输入确定的情况下,答案要么是yes,要么是no,且答案一旦确定就不会改变。但是停机问题不能这么做,因为停机问题没有指明特定输入,也就是说停机问题里面可能停机也可能不停,不能靠运行来判断)
2.三分法
三分搜索算法:和二分搜索类似,在待搜索的序列中,找到两个三分点,进行比较,从而把区间长度变成原来的1/3(如果原来的序列是单调的话)
参考代码:
exp=1e-10
def ternarySearch(left,right,key,array):
while right>=left:
# //得到的相除结果是整数
mid1=left+(right-left)//3
mid2=right-(right-left)//3
if abs(key-array[mid1])<exp:
return mid1
if abs(key-array[mid2])<exp:
return mid2
if key<array[mid1]:
right=mid1-1
elif key>array[mid2]:
left=mid2+1
else:
left=mid1+1
right=mid2-1
# 如果没有找到,返回-1
return -1
if __name__=='__main__':
nums=[1,2,3,4,5,6,7,8,9,10]
l=0
r=9
key=6
index=ternarySearch(l,r,key,nums)
print('Index of',key,'is',index)
key=66
index=ternarySearch(l,r,key,nums)
print('Index of',key,'is',index)
三分法的平均(最坏)时间复杂度是:
这和二分法的比较起来并没有快,比较最坏情况:
二分算法的开销(比较次数)满足:
故需要次比较
三分法:
故需要次比较,而
不过三分法可以做二分法处理不了的问题,因为二分法只能处理单调的数据,三分法除了处理单调数据外,还可以处理单峰(凸)数据(也就是有峰值,且峰值两边都单调的数据)(对具有凹特点的数据当然也可以用三分法)
处理方法大致为:按上述步骤找到mid1,mid2,然后比较mid1和mid2的大小,较大的那个说明更靠近峰值,然后舍去较小的mid对应的1/3区间
例子:
比如:给出圆锥体的表面积,在误差范围内求解圆锥体的最大体积
http://www.voidcn.com/article/p-rneuvsrj-s.html
3.延迟接受算法
在这里插入图片描述原书描述:
看不懂上面的描述没有问题,可以看下面的伪代码(网上的参考答案)
while里的第一个for循环,每个男的向自己心仪的妹子提婚,条件是在妹子曾经没有拒绝过他的情况下,妹子在男性心目中排名应当最靠前
while里的第二个for循环,轮到每个妹子从收到的提婚申请中挑选自己心目中排名最高的,然后把其他所有的对自己提婚男性加入黑名单(哈哈哈),当然这次挑选只是暂时的,因为只要while还没结束,就有可能有更心仪的男性取代现在被选中的男性
Here we assume that the men
are the suitors and the women the suitees.
procedure stable(M1, M2,...,Ms, W1, W2,...,Ws:
preference lists)
for i := 1 to s
mark man i as rejected
for i := 1 to s
set man i’s rejection list to be empty
for j := 1 to s
set woman j ’s proposal list to be empty
while rejected men remain
for i := 1 to s
if man i is marked rejected then add i to the
proposal list for the woman j who ranks highest
on his preference list but does not appear on his
rejection list, and mark i as not rejected
for j := 1 to s
if woman j ’s proposal list is nonempty then
remove from j ’s proposal list all men i
except the man i0 who ranks highest on her
preference list, and for each such man i mark
him as rejected and add j to his rejection list
for j := 1 to s
match j with the one man on j ’s proposal list
{This matching is stable.}
一些证明:
1.证明延迟接受算法可终止:
可以证明迭代的次数不超过,而且从上面可以看出终止的时候一定是一一匹配的
证明参考链接里面的那个数学归纳法(偷一波懒):
最坏情况的时间复杂度
2.证明延迟匹配算法总可以产生一个稳定的匹配:
假设算法不能产生一个稳定的匹配,也就是说,存在一个男的A,他相比妹子B',更喜欢妹子B,但是他却和B'结婚了,同时妹子B明明更喜欢A,却和A'结婚了,这就导致了不稳定,因为它把两情相悦的给拆开了。下面证明上述现象会产生矛盾:
根据算法描述,A一定会先向B进行提婚而不是B'(因为B优先级更高),但是上面假设A和B没有结婚,说明A被B拒绝了,根据算法描述,B之所以拒绝A,一定是遇到自己认为更好的,但是A'并不比A好,故矛盾,所以延迟匹配算法总可以产生一个稳定的匹配。
4.判断是否是的
-
证明: 是当且仅当在中,且在中。
证明:
充分性,如果是,那么存在实数,
当时,,也就是说,
, ,
所以在中,且在中。
必要性,如果在中,且在中。,那么, ; ,,取,则有当时,,
所以是
-
证明:在
显然有
-
证明:在
考虑
因为
故
-
判断是否是的
由前面3个命题得出 是的
5.矩阵连乘的最少乘法次数
26.给运行时间排序
3(源自 标题教材里面中文版P201)
(里面的当就行des~)
第一题排序:
比较,把根号整体换元成t即可看出
比较:
第二题排序:
4
网友评论