Oneton's Blog

0%

算法设计与分析 作业2

发表于 更新于 分类于 阅读次数： Valine：

第二周作业

1. 证：一张图的所有边权互不相同时，最小生成树唯一

假设$G$有两个不同的最小生成树$T$，$T’$，$e(T)=\{e_1, e_2,\cdots, e_m\}, e(T’)=\{e’_1, e’_2,\cdots, e’_m\}$

设$e_k$满足$e_k\neq e’_k$且$k$是满足条件的最小值，由于边权均不相同，不妨设$w(e_k)<w(e’_k)$

将$e_k$加入$T’$中，则$T’$会构成环，且满足环中不含边$e’_1, e’_2,\cdots, e’_{k-1}$（否则$T$中$e_1, e_2,\cdots, e_k$会构成环）

将$T’$中环任意非$e_k$的边删去即可得到比$T’$更小的生成树，与$T’$是最小生成树矛盾

得证。

2. Fredman & Tarjan算法

(a) 写出Fredman & Tarjan算法的伪代码

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
def Fredman_and_Tarjan(G):
	for u in G.Node:
        mark[u] = False

    while True:
        increase = False
        for u in G.Node:
            if not mark[u]:
                u_now = u
                break

        if u_now == None:
            break

        added_edge = Prim_Once(G, u_now)

        if added_edge == True or len(C[u_now]) >= K:
            for u in C[u_now]:
                mark[u] = True
            continue

    G_new = Contract_Nodes(G, C) # make connection a node
    if len(G_new.Node) <= 1:
        return G_new
    else:
    	return Fredman_and_Tarjan(G_new)

(b) 证明Fredman & Tarjan的时间复杂度是$O(m\log^*{n})$

一轮的时间代价为$O(m+n\log{K})$

每条边最多被枚举$2$次，时间代价$O(m)$

最多枚举$n$个点，寻找最小值时堆中最多有$K$个元素，代价$O(\log{K})$，这部分时间代价$O(n\log{K})$

所以，一轮的时间代价为$O(m+n\log{K})$

通过设定每轮$K_i$的值，实际一轮的时间代价为$O(m)$

首先有$2m=\sum\limits_{u}{d_u}=\sum\limits_i^l{\sum\limits_{u\in{C_i} } }{d_u}\geq\sum\limits_{i=1}^{l} {K}=Kl$，所以$l\leq \frac{2m}{K}$

我们设，在第$i$轮，有$n_i\leq n$个点，$m_i\leq m$个边，$K_i:=2^\frac{2m}{n_i}$

那么这一轮的时间代价为$O(m_i+n_i\log{K_i})=O(m_i+n_i\frac{2m}{n_i})=O(m)$

最多进行$\log^*{n}$轮

由于缩点，所以有$n_{i+1}<n_{i}<n, m_{i+1}<m_{i}<m$，所以$K_i\leq \frac{2m}{n_i+1}=\log{K_{i+1} }\Rightarrow K_{i+1}\geq 2^{K_i}$

也就是在$\log^*{n}$次后，$K$的值至少为$n$，此时这棵生成树已经有$n$个点了

所以，Fredman & Tarjan的时间复杂度是$O(m\log^*{n})$

3. Borůvka算法

(a) 写出Borůvka算法中，用$O(m)$的时间进行一轮缩点（contraction）的伪代码

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
def Contraction(G):
    G_new = new Graph()
    UF = new Union_Find()

    for e in G.E:
        if e.blue == True:
            if UF.fa[e.u] != UF.fa[e.v]:
                UF.union(e.u, e.v)
                
    for e in G.E:
        root_u = UF.fa[e.u]
        root_v = UF.fa[e.v]
        
        if root_u not in G_new.V:
            G_new.V.append(root_u)
        if root_v not in G_new.V:
            G_new.V.append(root_v)
            
        if root_u != root_v:
            if root_u > root_v:
                swap(root_u, root_v)
                
            if (root_u, root_v) not in G_new.E:
                G_new.E[(root_u, root_v)] = e.w
            else:
                G_new.E[(root_u, root_v)] = min(G_new.E[(root_u, root_v)], e.w)
        
        return G_new

(b) Borůvka算法每轮会把节点的数量减少一个常数倍，但是边的数量呢？构造一张$n$个节点$m$条边的图，使得在经过$\Omega(\log{n})$轮缩点后的图的边数依然是$\Omega(m)$，即便清除过重边和自环

不会，经过$\Omega(\log{n})$轮后，顶点数都趋近于$1$了，哪来的这么多边（

虽说如果是完全图的话，初始$m=n(n-1),O(m)=O(n^2)$，第$i$轮过后$m_i$最多也是$n_i(n_i-1)$。嗯，都是$O(n^2)$，合理…

(c) 证明运行$\log{\log{n} }$轮Borůvka算法后，使用斐波那契堆（Fibonacci Heap）实现的Prim算法求 MST的时间复杂度是$O(m \log{\log{n} })$

标记边一轮时间复杂度为$O(2m)$，缩点一轮时间复杂度为$O(m)$，运行$\log{\log{n} }$轮的时间复杂度为$O(m \log{\log{n} })$，最多剩余点数$n’$为$n’=\dfrac{n}{2^{\log{\log{n} } } }=\dfrac{n}{\log{n} }$，最多剩余边数$m’$为$O(m)$量级

当Prim算法使用斐波那契堆进行实现时，其时间复杂度为:

所以总时间复杂度$<O(m \log{\log{n}+m+n})=O(m \log{\log{n} })$

得证

4.

(a). 假设每个节点的邻接表已经按照边权升序排好。修改Borůvka算法使它的复杂度变为$O(m+n\log{n})$

缩点：直接枚举所有点，取邻接表中的第一条边进行缩边，单轮时间复杂度$O(n)$，缩点$\log{n}$轮的总时间复杂度为$O(n\log{n})$

连边：按先第$j$条边再第$i$个点的顺序枚举所有边，当枚举到某点连出去的边的边权比这个点所在连通块已知的连出的最大边权还大、且该连通块没有未连接的连通块时，遇到这个点就continue掉；当所有连通块都连接时可break；否则继续边权取min或连边。$O(m)$

总时间复杂度为$O(m+n\log{n})$

(b) 给定一个长度为$N$的序列和一个参数$k$，给出一个$O(N\log k)$的算法将序列分为$k$个组$g_1,g_2,\cdots,g_k$，每个组的元素个数最多$\lceil \frac Nk\rceil$，并且所有$g_i$中的元素均小于$g_{i+1}$中的元素

(c) 假设每个节点的领接表已经按照(b)中的算法排好序。修改(a)的算法使它的复杂度变为$O(m+\frac mk\log{n}+n\log{n})$

(d) 令$k=\log{n}$，证明：若$m\geq n\log{n}$，则(c)中的算法复杂度为$O(m\log{\log{n} })$。并给出一种算法， 使得对于任意$m$，都能达到$O(m\log{\log{n} })$

得证

Solution

相关文章
坚持原创技术分享, 您的支持将鼓励我继续创作!