前言

最近在学习NLP的过程中遇到了一个名词「主定理」，本来以为是一个非常简单的内容，仔细思考了一下发现自己没有听懂，然后就看了各种各样的内容，课程上有些不太能理解，所以决定写（水）一下这篇文章

假装开始

引言

归并排序

首先来看一道题目

有一个数组A = [3，4，1，6，7，2，5，9]，要对这个数组使用归并排序(Merge Sort)的方式进行排序，求这次排序的时间复杂度。

所谓归并排序，需要先将数组A分为B = [3，4，1，6]和C = [2，5，7，9]两部分，每个部分按照给定序次进行提前排序。

在排好序的B和C中对应位置进行比大小（即B[0]和C[0]，B[1]和C[1]，B[2]和C[2]，B[3]和C[3]），然后将所有数组排列好放回数组A中。

而对于分得的子数组进行排序时，由于每个子数组中元素个数不止2，因此在排序的时候采取相同的思路，将子数组按照相同的1/2方式分解成子数组，如此往复直到数组中只剩下2个元素，按照给定的顺序排好。

当所有元素个数为2的子数组排好序之后，按照自底向上的方式将结果进行组合和排序，直到组合成原来的数组结束。

对于这种方法，在编程实现中最方便的应该就是使用递归进行实现了，具体实现方式如下

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
29
30
31
32
33
34
def MergeSort(pendingList):
  """归并排序"""
  if(len(pendingList) <= 1): # 递归退出条件
    return pendingList
  else:
    middleIndex = len(pendingList) // 2  # 将数组分成更小的两个数组，返回中间值
    # 处理前后数组，分别返回两个排序好的两个数组
    frontList = MergeSort(pendingList[:middleIndex])
    backList = MergeSort(pendingList[middleIndex:])
    # 对排序好的两个数组合并，产生一个新的排序好的数组
    return ListMerge(frontList, backList)

def ListMerge(frontList, backList):
  """数组合并"""
  sortedList = []  # 初始化接收排序的数组
  i = 0  # 下标
  j = 0
  # 对两个数组中的元素 两两对比。
  # 将最小的元素，放到sortedList中，并对当前数组下标加1
  while (i < len(frontList) and j < len(backList)):
    if(frontList[i] <= backList[j]):
      sortedList.append(frontList[i])
      i += 1
    else:
      sortedList.append(backList[j])
      j += 1
  sortedList += frontList[i:]
  sortedList += backList[j:]
  return sortedList

pendingList = [3, 4, 1, 6, 7, 2, 5, 9]
print ('待排序数组为: ',pendingList)
sortedList = MergeSort(pendingList)
print ('排序完的数组为: ',sortedList)

那么其时间复杂度具体应该为多少呢？

我们首先假设排序数组A的时间复杂度为T(n)，那么将其分为两个则每组的复杂度会变成T(n/2)。两组合并时候由于要循环检测一遍之后插入相应的值，因此还应该再加一个复杂度为n。最终：T(n) = 2T(n/2) + n。

那么，怎样从上式得到标准的时间复杂度形如O()呢？

分治法

这种归并排序的处理方法隶属于一种专门的方法——分治法。

在计算机科学（CS，也就是我的专业）中，分治法是建基于多项分支递归的一种很重要的算法范型。就如同字面上的含义一样，是“分而治之”，即把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

正文部分

主定理（Master Theorem）定义

假设一个递归关系式有如下关系：

T(n)=a  T ⁣(nb)+f(n)T(n)=a\;T\!\left({\frac{n}{b}}\right)+f(n)，其中a≥1,  b>1a\geq1,\;b>1

其中，nn为问题规模，aa为递归的子问题数量，nb{\frac {n}{b}}为每个子问题的规模（假设每个子问题的规模基本一样），f(n)f(n)为将规模为n的子问题转换为a个规模为nb{\frac {n}{b}}的子问题，并且最终将所有子问题合并所需要的时间，其可以表示为f(n)=ndf(n)=n^d。

因此上式可以表示为

T(n)=a  T ⁣(nb)+ndT(n)=a\;T\!\left({\frac{n}{b}}\right)+n^d

归并排序的时间复杂度计算方法

对于引言中的归并排序，由于其转换为两个子问题，因此规模变为原来的一半，即n2{\frac{n}{2}}。分解和合并所有子问题的时间复杂度为O(n)，O(n)，因此该归并排序的递归的时间复杂度公式可以表示为：T(n)=2  T ⁣(n2)+O(n)T(n)=2\;T\!\left({\frac{n}{2}}\right)+O(n)

主定理证明

设：一个递归关系式有如下表示：

T(n)=a  T ⁣(nb)+ndT(n)=a\;T\!\left({\frac{n}{b}}\right)+n^d

在第0层中，所有子问题合并需要花费时间为：ndn^d

在第1层中，所有子问题合并需要花费时间为：子问题数量*每个子问题的子问题合并时间，即一共有a个子问题*每个子问题花费的时间(nb)d=O(a∗(nb)d))({\frac{n}{b}})^d = O(a * ({\frac{n}{b}})^d))

在第2层中，所有子问题合并需要花费时间为：子问题数量*每个子问题的子问题合并时间，即一共有(a*a个子问题)*(每个子问题花费的时间(nb2)d({\frac{n}{b^2}})^d，其等于a∗a∗(nb2)d=O(a2∗(nb2)d))a*a*({\frac{n}{b^2}})^d =O(a^2 * ({\frac{n}{b^2}})^d))

以此类推，最后合成第i层需要花费的时间为：ai∗(nbi)da^i*({\frac{n}{b^i}})^d

其每一层的复杂度表示如下表

层数复杂度
0ndn^d
1a∗(nb)da*({\frac{n}{b}})^d
2a2∗(nb2)da^2*({\frac{n}{b^2}})^d
……
iai∗(nbi)da^i*({\frac{n}{b^i}})^d

其分别对应不同层的内容

在第i层中，，每个问题的规模都是1。那么，从下往上推导，可知，在第i-1层中，所有子问题的规模为b，第i-2层中所有子问题的规模为b2b^2，以此类推，则第0层（即顶层）的规模应该为bib^i。

而又假设可知，最顶层的问题规模为n。

由此可以推得：bi=nb^i=n

∴i=log⁡bni={\log_{b} n}

∴T(n)=nd+a∗(nb)d+a2∗(nb2)d+...+ai∗(nbi)d=nd∗((abd)0+(abd)1+...+(abd)i)T(n)=n^d+a*({\frac{n}{b}})^d+a^2*({\frac{n}{b^2}})^d+ ... + a^i*({\frac{n}{b^i}})^d = n^d*((\frac a{b^d})^0+(\frac a{b^d})^1+...+(\frac a{b^d})^i)

即：T(n)=∑i=0i=iai∗(nbi)d=nd∗∑i=0i=i(abd)i{\displaystyle T(n)=\sum_{i=0}^{i=i}a^i\ast(\frac n{b^i})^d = n^d*\sum_{i=0}^{i=i}(\frac a{b^d})^i}

令q=abdq=\frac a{b^d}，则T(n)=nd∗∑i=0i=iqi{\displaystyle T(n)=n^d*\sum_{i=0}^{i=i}q^i}

∴T(n)=nd∗(q0+q1+...+qn)T(n)=n^d*(q^0+q^1+...+q^n)

此时需要分情况讨论q的取值，以1位分界线，因此共需要讨论3中情况：

①q=1q=1，即a=bda=b^d
则T(n)=nd(i+1)=nd(logbn+1)=O(nd∗logbn)T(n)=n^d(i+1)=n^d(log_{b} n+1)=O(n^d*log_{b} n) (此处忽略了常数1)

当q≠1q≠1时，(q0+q1+...+qn)(q^0+q^1+...+q^n)部分构成等比数列，因此此部分可以用等比数列求和公式Sn=a1(1−qn)1−qS_{n}={\frac {a_1(1-q^{n})}{1-q}} 进行计算

在这里Sn=a1(1−qn)1−q=q0(1−qi+1)1−q=1−qi+11−qS_{n}={\frac {a_1(1-q^{n})}{1-q}}={\frac {q^0(1-q^{i+1})}{1-q}}={\frac {1-q^{i+1}}{1-q}}

② 当q<1q<1时，即a<bda<b^d时，i+1i+1非常大，因此lim⁡(i+1)→∞qi+1=0{\displaystyle \lim _{(i+1)\to \infty }q^{i+1}=0}，所以lim⁡(i+1)→∞1−qi+1=1{\displaystyle \lim _{(i+1)\to \infty }1-q^{i+1}=1}

则T(n)≈nd1−q=C∗nd=O(nd)T(n)\approx\frac {n^d}{1-q}=C*n^d=O(n^d)

③ 当q>1q>1时，即a>bda>b^d时，i+1i+1非常大，因此lim⁡(i+1)→∞qi+1=∞{\displaystyle \lim _{(i+1)\to \infty }q^{i+1}=\infty}，所以lim⁡(i+1)→∞1−qi+1=−qi+1{\displaystyle \lim _{(i+1)\to \infty }1-q^{i+1}=-q^{i+1}}，lim⁡(i+1)→∞1−q=−q{\displaystyle \lim _{(i+1)\to \infty }1-q=-q}

则T(n)≈nd∗1−qi+11−q{\displaystyle T(n)\approx n^d * {\frac {1-q^{i+1}}{1-q}}}

=nd∗qi{\displaystyle = n^d * q^i }

=nd⋅(abd)logbn{\displaystyle = n^d \cdot (\frac {a}{b^d})^{log_b n} }

=nd⋅alogbnb(logbn)⋅n{\displaystyle = n^d \cdot {\frac {a^{log_b n}}{b^{(log_b n)\cdot n}}} }

=alogbn{\displaystyle = a^{log_b n}}

根据对数运算性质alogbn=nlogbaa^{log_b n} = n^{log_b a}，可得：

=nlogba{\displaystyle = n^{log_b a}}

综上①②③可得：

T(n)={O(nd)a<bdO(ndlog⁡bn)a=bdO(nlogba)a>bd\begin{array}{l}T(n)=\left\{\begin{array}{lc}O(n^d)&a<b^d\\O(n^d\log_bn)&a=b^d\\O(n^{log_ba})&a>b^d\end{array}\right.\\\end{array}

应用和例题

1、T(n)=3T(n/2)+n2T(n) = 3T(n/2) + n^2

nlogba=nlog23≈n1.6n^{log_b a}=n^{log_2 3}\approx n^{1.6}

f(n)=n2f(n) = n^2

因此：nlogba≈n1.6<n2=f(n)n^{log_b a} \approx n^{1.6} < n^2 = f(n)，即nlogba<f(n)n^{log_b a} < f(n)。此时满足第三种情况，即T(n)=f(n)=O(n2)T(n) = f(n) = O(n^2)

2、T(n)=4T(n2)+n2T(n) = 4T(\frac n 2) + n^2

nlogba=nlog24=n2n^{log_b a} = n^{log_2 4} = n^2

f(n)=n2f(n) = n^2

因此：nlogba=n2=f(n)n^{log_b a} = n^2 = f(n)，即nlogba=f(n)n^{log_b a} = f(n)。此时满足第二种情况，即T(n)=O(ndlogbn)=O(n2log2n)T(n) = O(n^{d}log_{b} n)=O(n^{2}log_{2} n)

3、T(n)=2T(n2)+nT(n) = 2T(\frac n 2) + n

此时：a = 2, b = 2

nlogba=nlog22=n=f(n)n^{log_b a} = n^{log_2 2} = n = f(n) => Case 2

∴T(n)=O(n1log2n)=O(n⋅log2n)T(n)=O(n^{1}log_{2} n)=O(n \cdot log_{2} n)

参考

[bilibili]【学习记录】分治和主定理的推导-计算机算法：https://www.bilibili.com/video/BV1Q7411R7rk

[CSDN]Master—Theorem 主定理的证明和使用：https://blog.csdn.net/jmh1996/article/details/82827579

[wikipedia]Divide-and-conquer_algorithm：https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm

[cnblogs]图解排序算法(四)之归并排序:https://www.cnblogs.com/chengxiao/p/6194356.html

[bilibili]贪心 NLP 自然语言处理：https://www.bilibili.com/video/BV1yK4y1E7n4

[wikipedia]Master theorem (analysis of algorithms)：https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)