稳定脱单问题（延迟接受算法）

2019-12-06 本文已影响0人赫尔特

Discrete mathematics and its applications 7th 第三章笔记

文章目录

$\color{orange}{1.停机问题(The Halting Problem)}$
$\color{red}{2.三分法}$
$\color{green}{3.延迟接受算法}$
$\color{pink}{4.判断logn!log n!logn!是否是Θ(nlogn)\Theta (nlogn)Θ(nlogn)的}$
$\color{purple}{5.矩阵连乘的最少乘法次数}$
$\color{blue}{6.给运行时间排序}$

算法及其复杂度分析

说明：笔记并不完整，只记录了书本的部分。

1.停机问题(The Halting Problem)

停机问题是 “证明存在不可解问题” 的一个例子

问题描述：

是否存在这样一个过程，该过程能以一个计算机程序以及该程序的一个输入作为输入，并判断在给定输入运行时是否最终停止。

原书证明（反证法）：

1
最后与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)

三分法的平均（最坏）时间复杂度是: $O(log_3n)$
这和二分法的 $O(log_2n)$ 比较起来并没有快，比较最坏情况：
二分算法的开销（比较次数）满足： $T(n)=T(n/2)+2,T(1)=1$
故需要 $2log_2n+1$ 次比较
三分法： $T(n)=T(n/3)+4,T(1)=1$
故需要 $4log_3n+1$ 次比较，而 $4log_3n=\frac{4log_2n}{log_23}\ge2log_2n$

不过三分法可以做二分法处理不了的问题，因为二分法只能处理单调的数据，三分法除了处理单调数据外，还可以处理单峰（凸）数据（也就是有峰值，且峰值两边都单调的数据）（对具有凹特点的数据当然也可以用三分法）

处理方法大致为:按上述步骤找到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.证明延迟接受算法可终止：

可以证明迭代的次数不超过 $n^2-2n+2$ ，而且从上面可以看出终止的时候一定是一一匹配的
证明参考链接里面的那个数学归纳法（偷一波懒）:
最坏情况的时间复杂度

2.证明延迟匹配算法总可以产生一个稳定的匹配：

假设算法不能产生一个稳定的匹配，也就是说，存在一个男的A,他相比妹子B',更喜欢妹子B,但是他却和B'结婚了，同时妹子B明明更喜欢A，却和A'结婚了，这就导致了不稳定，因为它把两情相悦的给拆开了。下面证明上述现象会产生矛盾：
根据算法描述，A一定会先向B进行提婚而不是B'（因为B优先级更高），但是上面假设A和B没有结婚，说明A被B拒绝了,根据算法描述，B之所以拒绝A，一定是遇到自己认为更好的，但是A'并不比A好，故矛盾，所以延迟匹配算法总可以产生一个稳定的匹配。

4.判断 $log n!$ 是否是 $\Theta (nlogn)$ 的

证明: $f(x)$ 是 $\Theta(g(x))$ 当且仅当 $f(x)$ 在 $O(g(x))$ 中，且 $g(x)$ 在 $O(f(x))$ 中。

证明：
充分性，如果 $f(x)$ 是 $\Theta(g(x))$ ,那么存在实数 $C_1,C_2$ ,
当 $x>k$ 时， $C_1|g(x)|\le|f(x)|\le C_2|g(x)|$ ，也就是说，
$|g(x)|\le \frac1C_1|f(x)|$ , $|g(x)|\ge \frac1C_2|f(x)|$ ，
所以 $f(x)$ 在 $O(g(x))$ 中，且 $g(x)$ 在 $O(f(x))$ 中。

必要性，如果 $f(x)$ 在 $O(g(x))$ 中，且 $g(x)$ 在 $O(f(x))$ 中。，那么 $|g(x)|\le \frac1C_1|f(x)|$ ， $x>k_1$ ; $|g(x)|\ge \frac1C_2|f(x)|$ ， $x>k_2$ ,取 $k=max\{k_1,k_2\}$ ,则有当 $x>k$ 时， $C_1|g(x)|\le|f(x)|\le C_2|g(x)|$ ，
所以 $f(x)$ 是 $\Theta(g(x))$

证明： $log n!$ 在 $O(nlogn)中$

显然有 $n!<n^n$

证明： $nlogn$ 在 $O(log n!)中$

考虑 $(n!)^2=(n\cdot1)\cdot((n-1)\cdot2)\cdot((n-2)\cdot3)\cdot\cdot\cdot(1\cdot n)$
因为 $0\le i\le n-1时，(n-i)\cdot(i+1)-n=i\cdot(n-i-1)\ge0$
故 $(n!)^2\ge n^n$

判断 $log n!$ 是否是 $\Theta (nlogn)$ 的

由前面3个命题得出 $log n!$ 是 $\Theta (nlogn)$ 的

5.矩阵连乘的最少乘法次数

参考链接

6.给运行时间排序

（源自标题教材里面中文版P201）

(里面的 $logn$ 当 $log_2n$ 就行des~)
第一题排序：
$(logn)^2,2^{\sqrt{log_2n}},n(logn)^{1001},n^{1.0001},1.0001^n,n^n$
比较 $(logn)^2,2^{\sqrt{log_2n}}$ ，把根号整体换元成t即可看出
比较 $n(logn)^{1001},n^{1.0001}$ ：