Skip to content

7 Divide and Conquer

主定理（\(f(N)\) 形式）

对于递推关系 \(T(N) = aT\left(\frac{N}{b}\right) + f(N)\):

  • 若对于常数 \(\kappa < 1\)，有 \(a f\left(\frac{N}{b}\right) = \kappa f(N)\) 成立，则 \(T(N) = \Theta(f(N))\)
  • 若对于常数 \(K > 1\)，有 \(a f\left(\frac{N}{b}\right) = K f(N)\) 成立，则 \(T(N) = \Theta(N^{\log_b a})\)
  • 若 \(a f\left(\frac{N}{b}\right) = f(N)\) 成立，则 \(T(N) = \Theta(f(N) \log_b N)\)

主定理（\(\Theta(N^k \log^p N)\) 形式）

对于递推关系 \(T(N) = aT\left(\frac{N}{b}\right) + \Theta(N^k \log^p N)\)，其中 \(a \geq 1, b > 1, k \geq 0\)，\(p\) 为任意实数，那么：

  • 若 \(a > b^k\)，则 \(T(N) = \Theta(N^{\log_b a})\)
  • 若 \(a = b^k\)，则
    • 若 \(p > -1\)，\(T(N) = \Theta(N^k \log^{p+1} N)\)
    • 若 \(p = -1\)，\(T(N) = \Theta(N^k \log \log N)\)
    • 若 \(p < -1\)，\(T(N) = \Theta(N^k)\)
  • 若 \(a < b^k\)，则
    • 若 \(p \geq 0\)，\(T(N) = \Theta(N^k \log^p N)\)
    • 若 \(p < 0\)，\(T(N) = \Theta(N^k)\)

分治法在排序算法中的应用

How many of the following sorting methods use(s) Divide and Conquer algorithm?

  • Heap Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort
  • Selection Sort
  • Shell Sort
答案

使用分治算法的排序方法是归并排序和快速排序，共 \(2\) 个

Let \(T(n)\) be the running time of quicksort on an input of size \(n\). We already know that \(T(n)\) is a random variable whose value depends on the random choices of quicksort, and that the expectation of \(T(n)\) is \(O(n\log n)\). Is the following statement true or false?

The minimum possible value of \(T(n)\) can be as small as \(\Theta(n)\), and the maximum possible value can be as large as \(\Theta(n^2)\).

答案

对于最优情况，每次选择的 pivot 是中位数，划分出的子数组规模接近相等，由 \(T(n) = 2T(n/2) + \Theta(n)\) 得 \(T(n) = \Theta(n\log n)\)

对于最坏情况，每次选择的 pivot 是当前数组的最大/最小元素，划分出的子数组规模为 \(n-1\) 和 \(0\)，由 \(T(n) = T(n-1) + \Theta(n)\) 得 \(T(n) = \Theta(n^2)\)

综上，答案为 \(\textnormal{F}\)

主定理的简单应用

Considering the view point of treating function \(T(n) = aT(n/b) + n^r\) as a recursion tree. If \(T(n) = O(n^r)\), then the time cost is dominated by the root of the tree.

答案

\(\textnormal{T}\)

3-way-mergesort: Suppose instead of dividing in two halves at each step of the mergesort, we divide into three one thirds, sort each part, and finally combine all of them using a three-way-merge. What is the overall time complexity of this algorithm?

答案

由题意得：\(T(n) = 3T(\frac{n}{3}) + O(n)\)，运用主定理可得：\(T(n) = O(nlogn)\)，故答案为 \(\textnormal{D}\)

The asymptotic upper bound for the recurrence \(T(n) = 2T(\lfloor n/2 \rfloor + 17) + n\) is \(T(n) = O(n \log n)\).

答案

向下取整 \(\lfloor n/2 \rfloor\) 和常数偏移 \(+17\) 这两个修饰项属于渐近分析中的低阶扰动，不会改变递推式的核心增长趋势，可直接应用主定理，故答案为 \(\textnormal{T}\)

For the recurrence equation \(T(N) = aT(N/b) + f(N)\), if \(af(N/b) = f(N)\), then \(T(N) = \Theta(f(N)\log_b N)\).

答案

\(f(N) = a f(N/b) = a^2 f(N/b^2) = \dots = a^k f(1)\)，

其中 \(N = b^k\)，即 \(k = \log_b N\)，则有：

\[ f(N) = a^{\log_b N} f(1) = N^{\log_b a} f(1) \]

因此 \(f(N) = \Theta(N^{\log_b a})\)，\(T(N) = aT(N/b) + \Theta(N^{\log_b a})\)，

运用主定理可得 \(T(N) = \Theta(f(N)\log_b N)\)，答案为 \(\textnormal{T}\)

Consider the following function, where the time complexity for function calc() is \(O(1)\).

void fun(int l, int r) {
    if(r-l+1<=1234) return;
    int m=(l+r)/2;
    int m1=(l+m)/2, m2=(m+1+r)/2;
    fun(l, m);
    fun(m1+1, m2);
    for(int k=1;k<=r-l+1;k++)
        for(int i=1;i<=r-l+1;i++)
            for(int j=l;j<=r;j+=i)
                calc(j, i);
    fun(m+1, r);
    fun(m1+1, m2);
}

Assume the initial input is l=1, r=N, What is the running time of this function? Your answer should be as tight as possible.

答案

由 \(T(N) = 4 T(\frac{N}{2}) +O(N^2 \log N)\) 得 \(T(N) = O(N^2 \log ^2 N)\)

\(\sqrt{N}\) 相关的主定理的应用

To solve a problem with input size \(N\) by divide and conquer, an algorithm divides the problem into 2 subproblems with size \(\sqrt N\) (assuming it is an integer ) and the time recurrences is \(T(N) = 2T(\sqrt N)+\log(N)\). What is the overall time complexity of this algorithm?

答案

令 \(n = 2^m\)，\(S(m) = T(2^m)\)，则 \(S(m) = 2S(\frac{m}{2}) + m\)，\(S(m) = O(m \log m)\)，\(T(n) = O(\log N \log \log N)\)

To solve a problem with input size \(N\) by divide and conquer, an algorithm divides the problem into 3 subproblems with size \(\sqrt N\) (assuming it is an integer ) and the time recurrences is \(T(N) = 3T(\sqrt N)+\log (N)\). What is the overall time complexity of this algorithm?

答案

同理有 \(S(m) = 3S(\frac{m}{2}) + m\)，\(S(m) = O(m ^{log_2 3})\)，\(T(n) = O((\log N)^{\log_ 2 3})\)

Recall that in the merge sort, we divide the input list into two groups of equal size, sort them recursively, and merge them into one sorted list. Now consider a variant of the merge sort. In this variant, we divide the input list into \(\sqrt{n}\) groups of equal size, where n is the input size. What is the worst case running time of this variant? (You may use the fact that merging \(k\) sorted lists takes \(O(m \log k)\) where \(m\) is the total number of elements in these lists.)

答案

由已知得 \(T(n) = \sqrt{n} \cdot T(\sqrt{n}) + O(n \log \sqrt{n}) = \sqrt{n} T(\sqrt{n}) + O(n \log n)\)

令 \(n = 2^m\)，则 \(S(m) = T(2^m)\)，\(S(m) = 2^{\frac{m}{2}} \cdot S\left(\frac{m}{2}\right) + O(2^m \cdot m)\)

对 \(S(m)\) 进行多次迭代展开，最终得到：

\[ S(m) = 2^{m \cdot (1 - \frac{1}{2^k})} \cdot S(1) + O\left(2^m \cdot m \cdot \left(1 + \frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^{k-1}}\right)\right) \]

其中 \(k = \log m\)，则 \(S(m) = O(2^m) + O(2^m \cdot m) = O(n \log n)\)

矩阵快速幂

The \(n\)-th Fibonacci number can be computed by divide and conquer method of computing \(x^n\), where \(x\) is the matrix \(\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}\). Then the \(n^2\)-th Fibonacci number \(F_{n^2}\) can be computed in \(O(\log n)\) time.

答案

矩阵快速幂（分治法）的时间复杂度为 \(O(\log k)\)，其中 \(k\) 是幂次，则计算 \(F_{n^2}\) 的时间复杂度 \(= O(\log (n^2)) =O(\log n)\)，答案为 \(\textnormal{T}\)

Then the \(n^3\text{-th}\) Fibonacci number \(F_{n^3}\) can be computed in \(O(\log n)\) time.

答案

\(\textnormal{T}\)

矩阵乘法

Given two \(n \times n\) matrices \(A\) and \(B\), the time complexity of the simple matrix multiplication \(C = A \cdot B\) is \(O(n^3)\). Now let's consider the following Divide and Conquer idea:

Divide each matrix into four \(\frac{n}{2} \times \frac{n}{2}\) submatrices as follows: \(\begin{bmatrix} C_ 1 & C_ 2 \\ C_ 3 & C_ 4\end{bmatrix}\) = \(\begin{bmatrix} A_ 1 & A_ 2 \\ A_ 3 & A_ 4 \end{bmatrix} \cdot \begin{bmatrix} B_ 1 & B_ 2\\ B_ 3 & B_ 4 \end{bmatrix}\)

We recursively calculate each block of \(C\) as \(C_1 = A_1 \cdot B_1 + A_2 \cdot B_3\) and so on. This can reduce the time complexity of the simple calculation.

答案

\(T(n) = 8T\left(\frac{n}{2}\right) + O(n^2)\)，由主定理得 \(T(n) = O(n^3)\)，与简单矩阵乘法的时间复杂度相同，并未降低，答案为 \(\textnormal{F}\)

Givien two \(n\times n\) matrices \(A\) and \(B\). Let's consider the following Divide and Conquer idea to do matrix multiplication \(C = A \cdot B\). Divide each matrix into four \(\frac{n}{2}\times\frac{n}{2}\) submatrics as follows: \(\begin{bmatrix} C_ 1 & C_ 2 \\ C_ 3 & C_ 4\end{bmatrix}\) = \(\begin{bmatrix} A_ 1 & A_ 2 \\ A_ 3 & A_ 4 \end{bmatrix} \cdot \begin{bmatrix} B_ 1 & B_ 2\\ B_ 3 & B_ 4 \end{bmatrix}\) . We define \(P_ 1, P_ 2, \cdots ,P_ 7\) as follows:

\(P_ 1 = A_ 1\cdot(B_ 2-B_ 4)\)，\(P_ 2 = (A_ 1+A_ 2)\cdot B_ 4\)，\(P_ 3 = (A_ 3+A_ 4)\cdot B_ 1\)，\(P_ 4 = A_ 4\cdot(B_ 3-B_ 1)\)

\(P_ 5 = (A_ 1+A_ 4)\cdot(B_ 1+B_ 4)\)，\(P_ 6 = (A_ 2-A_ 4)\cdot(B_ 3+B_ 4)\)，\(P_ 7 = (A_ 1-A_ 3)\cdot(B_ 1+B_ 2)\)

Here all the matrix multiplications are done recursively. Then each part of \(C\) can be calculated by simple additions and subtractions among \(P_ 1, P_ 2, \cdots ,P_ 7\). Which of the following is the closest to the actual time complexity?

\(\textnormal{A}\). \(O(n^2\log_ 2 n)\) \(\qquad\) \(\textnormal{B}\). \(O(n^e)\) \(\qquad\) \(\textnormal{C}\). \(O(n^{\log_ 2 7})\) \(\qquad\) \(\textnormal{D}\). \(O(n^3)\)

答案

两个 \(k \times k\) 的矩阵加减需 \(O(k^2)\) 时间，则 \(T(n) = 7T(\frac{n}{2}) + O(n^2)\)，运用主定理得到答案为 \(\textnormal{C}\)

Closest Points Problem

Recall that, to solve the closest pair problem, the first step of the divide-and-conquer algorithm divides the point set into \(L\) and \(R\) according to the x-coordinate. Is the following statement true of false?

In the combine step of this algorithm, it is always able to find the closest pair with one point in \(L\) and the other in \(R\).

答案

\(\textnormal{F}\)

If divide-and-conquer strategy is used to find the closest pair of points in a plane, unless the points are sorted not only by their \(x\) coordinates but also by their \(y\) coordinates, it would be impossible to solve it in a time of \(O(N log N)\), where \(N\) is the number of points.

答案

\(\textnormal{T}\)