问题描述

给定无重边,正边权,无向图 \(G = (V, E)\),求 \(G\) 的边权和最小的连通生成子图。

如果,每个点的度没有限制,那么就相当于求 \(G\) 的最小生成树,存在多项式时间最优算法。

但如果,每个点的度存在限制,这个问题就没有那么简单了。

不妨设第 \(i\) 个点的度为 \(deg(i)\),度限制为 \(d(i)\)

那么就有如下两个问题:

问题一:求 \(G\) 的边权和最小的连通生成子图,且 \(deg(i) \leq d(i)\)

问题二:求 \(G\) 的边权和最小的连通生成子图,且 \(deg(i) = d(i)\)

显然,对于问题二,如果所有的 \(d(i) = 2\),那么这个问题相当于 TSP 问题。

不幸的是,这两个问题都是 NP-hard 的,甚至目前没有找到多项式时间的近似算法。

但是,我们可以对 \(G\) 加一些限制条件,使得多项式时间的近似算法成为可能。

问题重述

给定无重边,正边权,无向完全图 \(G = (V, E)\),且边集满足三角形不等式。

问题一 (BMST):求 \(G\) 的边权和最小的连通生成子图,且 \(deg(i) \leq d(i)\)

问题二 (ConnFact):求 \(G\) 的边权和最小的连通生成子图,且 \(deg(i) = d(i)\)

Read More

其实求 \(x\) 以内素数个数,有时间复杂度为 \(O(x^{2/3}loglogx)\),空间复杂度为 \(O(x^{1/3})\)优秀算法

\(prime(i)\) 表示第 \(i\) 个素数。

\(\pi(x)\) 表示小于等于 \(x\) 的素数个数。

\(\phi(x, a)\) 表示小于等于 \(x\) 的数中,不被前 \(a\) 个素数整除的数的个数,特别地,\(\phi(x, 0) = x\)

\(\phi(x, a)\) 分类,其中 \(P_k(x, a)\) 表示小于等于 \(x\) 的数中,不被前 \(a\) 个素数整除且有且仅有 \(k\) 个素数因子的数的个数,特别地,\(P_0(x, a) = 1\)。那么有,\(\phi(x,a) = P_0(x, a) + P_1(x, a) + \dots + P_k(x, a) + \dots\)

考虑到,

\[\pi(x) = P_1(x, a) + a = \phi(x, a) - P_0(x, a) - \sum_{k = 2}^{\infty}P_k(x, a) + a = \phi(x, a) -1 - \sum_{k = 2}^{\infty}P_k(x, a) + a\]

所以,对于特定的 \(a\),我们只需要知道 \(\phi(x, a)\)\(\sum_{k = 2}^{\infty}P_k(x, a)\),就可以计算出 \(\pi(x)\)

\(a = \pi(x ^ {1 / 3})\),那么 \(P_3(x, a) = P_4(x, a) = \dots = 0\),也就是说我们只需要计算 \(\phi(x, a)\)\(P_2(x, a)\)

先考虑如何计算 \(\phi(x, a)\)

注意到 \(\phi(x, a - 1)\)\(\phi(x, a)\) 多了那些不被前 \(a - 1\) 个素数整除但可以被 \(prime(a)\) 整除的数,即多了 \(\phi(\frac{x}{prime(a)}, a - 1)\)。因此,\(\phi(x, a) = \phi(x, a - 1) - \phi(\frac{x}{prime(a)}, a - 1)\)

我们解这个递归式就可以计算出 \(\phi(x, a)\)

假设我们能够解这个递归式,那么我们如何计算时间复杂度呢?

因为这个递归树是一棵满二叉树,所以叶子结点个数 \(n_0\) 与非叶结点个数 \(n_2\) 满足 \(n_0 = n_2 + 1\),也就是说时间复杂度为 \(O(n_0 + n_2) = O(2n_0 - 1) = O(n_0)\),因此我们只需要考虑递归树的叶子结点就好了。

因为递归树上的任一结点都可以被唯一地表示为 \(\phi(\frac{x}{n}, b)\),那么有一个显然的递归边界如下:

  1. \(b = 0\)\(\phi(\frac{x}{n}, b) = \frac{x}{n}\)
  2. \(\frac{x}{n} \leq prime(b)\)\(\phi(\frac{x}{n}, b) = 1\)

不过可以证明,这样的递归边界会使时间复杂度至少为 \(\Omega(\frac{x}{log^3x})\)。考虑 \(n\)\(3\) 个小于等于 \(x^{1/3}\) 的素数的乘积,由于 \(prime(b) \leq x^{1/3}\),因此必定存在叶子结点 \(\phi(\frac{x}{n}, b)\)。根据素数定理,小于等于 \(x^{1/3}\) 的素数大概有 \(\frac{x^{1/3}}{logx^{1/3}}\) 个,故递归树至少有 \(\Omega(\frac{x}{log^3x})\) 个叶子结点,达不到之前所说 \(O(x^{2/3}loglogx)\) 这样的时间复杂度。

现在考虑修改递归边界如下:

  1. \(b = 0\) 并且 \(n \leq x^{1/3}\)
  2. \(n > x^{1/3}\)

Read More

\(B_n\) 表示将 \(n\) 个不同的元素划分为若干非空集合的方案数。

递推式:\(B_{n + 1} = \sum_{k = 0}^nC(n, k)B_k\)

证明:考虑第 \(n+1\) 个元素,可以把它和 \(k\) 个其他元素划分在一起,那么剩余 \(n - k\) 个元素有 \(B_{n - k}\) 种划分。

递推式:\(B_n = \sum_{k = 0}^n Stirling2(n, k)\)

证明:\(Stirling2(n, k)\) 表示将 \(n\) 个不同的元素划分为 \(k\) 个非空集合的方案数。

Bell 三角

1

1 2

2 3 5

5 7 10 15

15 20 27 37 52

  1. \(b(0, 0) = 1\)
  2. \(b(i, 0) = b(i - 1, i - 1)\)
  3. \(b(i, j) = b(i, j - 1) + b(i - 1, j - 1)\)

Read More