分析分治法

经过了昨天的一小波插入算法的分析，相信你已经对计算时间复杂度有了一定的理解，接下来我们稍稍深入一点，开始研究下分治法下的算法该如何计算他的时间复杂度，首先我们从merge-sort算法开始。

def merge(Array):
    mid = length.Array/2                  #a
    X = Array[1:mid]                      #a
    Y = Array[mid+1:length.Array]         #a
    y = mid + 1                           #a
    x = 0                                 #a
    i = 0                                 #a
    while x <= mid and y <= length.Array: #a*(n-1)
        if X[x] < Y[y]:                   #a*(n-1)/2
            Array[i] = X[x]               #a*(n-1)/2
            i += 1                        #a*(n-1)/2
            x += 1                        #a*(n-1)/2
        else:                             #a*(n-1)/2
            Array[i] = Y[y]               #a*(n-1)/2
            i += 1                        #a*(n-1)/2
            y += 1                        #a*(n-1)/2
    if x > mid:                           #a
        Array[i:] = Y[y:]                 #a
    elif y > length.Array:
        Array[i:] = X[x:]

这是merge-sort算法中的合并步骤的伪代码（但愿我没写错），我们先分析一下这一部分的时间复杂度。同样我们假设所有的代码执行时间相同都为a（当然我这里是偷懒做法，很显然每一行代码执行所需的时间不同，但最后也都只是影响项集前的系数，都会被我们给忽略掉）。这里我们还是考虑最差的一种情况，也就是进行分治排序的时候把两边数组基本上都走完了。让我们把所需时间相加起来得出T(n)=5an+3a，也就是O(n)，易知（屠龙勇士终成恶龙）Ω(n),所以θ(n)。看起来挺不错的，只是个线性复杂度，但这才刚刚开始，这个算法还有一部分呢。

def merge_sort(Array):                   
    if length.Array = 1:                     
        return Array                         
    else:
        mid = length.Array/2                                     
        merge_sort(Array[0:mid])
        merge_sort(Array[mid+1:length.Array])
        merge(Array)

这个该如何计算呢？一环套一环，圈圈绕绕的。首先，很明显的就是当数组长度为一的时候，它就执行一次，并不会递归，所以这时候的T(n) = 2a,也就是Θ(1)，（虽然文中指出这样使用是不符合数学逻辑的，但大家又都这样使用，那我们为什么不呢？数学的事情就让他们研究数学的去头疼吧）是常数级的。那么递归的时候我们该怎么考虑呢？首先，我们知道merge_sort处理一个n规模的数组他所需的时间函数表达式为T(n)，至于表达式具体怎么写我们不着急，然后我们的merge_sort算法是将n规模的数组拆分成两部分进行简化然后再处理，那么很明显，每部分只需要处理n/2，那么时间函数表达式应该就为T(n/2),那么两部分就应该是2T(n/2)，这时候就初见端倪了，我们可以写出一部分函数表达式了T(n) = 2T(n/2) + D(n) +C(n)。

当中的D(n)与C(n)又是两个时间的函数表达式，代表着除了递归部分之外的代码操作所需的时间，例如：D(n)可以表示为代码中的mid计算时间，显然是θ(1),C(n)可以用来表达merge函数执行所需的时间也就是θ(n),那么D(n) +C(n)就可以简化成θ(n)了，加一个参数项不影响线性函数，所以还是θ(n)。那么我们的时间函数表达式就可以写T(n) = 2T(n/2) +θ(n)了，虽然我们还是没有计算出来，但也是有所进展。

上图就是常见的递归式，和我们上面的例子结合解释一下，n<=c指的是当我们输入的规模一定小的时候，整个算法运行的时间就是一个常量，在merge_sort算法中，当输入数组元素为一的时候就符合这种情况。其他情况下，D(n) +C(n)就是除去递归其他部分所需的时间，aT(n/b),指的就是将问题规格如何化简进行递归，像上文中的就是将数组划分为两部分，每一部分都是原来的一半，所以aT(n/b)的意思就是将问题化简为a个子问题，每个子问题的规格是原问题的1/b。

计算递归式

递归式的计算方法有三种，分别是代入法，递归树法，主方法，下文我们以T(n) = 2T(n/2) +θ(n)为实例挨个介绍。

代入法

我们猜测一个界然后用数学归纳法证明这个界是正确的。

代入法的精髓就是猜测，但是谁能猜得到啊，所以这个方法是一种十分依赖个人经验的方法，或者你也有神托梦给你答案。由于哥们是先知（手动滑稽），所以这里我们直接猜测T(n) = 2T(n/2) +θ(n)的上界是O(nlgn)(需要注意的是，在计算机科学中lg就是log₂，而不是log₁₀)，所以我们需要一个参数c>0使得T(n)<=c*n*lgn。接下来我们带入到式子中:

T(n)<=2*c*(n/2)*lg(n/2) +θ(n)
=c*n*lg(n/2) + θ(n)
= c*n*(lgn-lg2) + θ(n)
= c*n*lgn - c*n + θ(n)
<= c*n*lgn

最后一个不等式c*n*lgn - c*n + θ(n)<= c*n*lgn在c>=1的情况下成立。因为我们可以将θ(n)视为n，这是可行的。下文中我都会将θ(n)视为n。

当然我们都不是天才，也没有神来托梦，直接下来我们来猜测一下最可能想到的O(n²),毕竟我们的插入算法的时间复杂度就是这个，所以我们需要一个常数c>0使得T(n)<=c*n²。接下来带入式子中：

T(n)<=2*c*(n/2)² + θ(n)
=c*n² / 2 + θ(n)
<= c*n²

最后一个不等式c*n² / 2 + θ(n)<= c*n²在c>=2/n的情况下成立。显然这是错误的，我们需要一个常数c。

递归树

将递归式转化为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。

上图就是T(n) = 2T(n/2) +θ(n)的递归树，当我们第一次执行该算法的时候，产生了n的运行时间和两个T(n/2)新分支，如图a，后面T(n/2)又产生了n/2的运行时间和T(n/4)的新分支，如图b，如此递推直到最底层T(1）。那么我们可以知道这个树的的高度就是lgn，而将每一层所需的时间加在一起就是每次递归所需的时长，最后相乘便得到了T(n) = nlgn，也就是O(nlgn)。这里指出几点，每次递归有几个分支是由T(n/2）前的系数决定的，如果为3，那么每次就应该是三个分支，n/2是每次递归传下的规模。所以简单归纳一下，对于T(n) = aT(n/b) + C(n) + D(n),a所决定的是分支数，C(n) + D(n)决定的是树顶大小，n/b决定是每次传下去的规模，用n/b替换掉C(n) + D(n)中的n就是下面分支的时间消耗，最后我们拿树高乘以每层所需的时间消耗就能的到整棵树的代价。