数据结构与算法之美-主定理方法(master theorem)和

1. Merge Sort - 归并排序

核心：归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取后相应指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

归并排序的分析

1. Python代码实现

"""
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

最好时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
稳定性：稳定
"""

class Sort(object):

    def mergeSort(self, alist):
        n = len(alist)

        if n <= 1:
            return alist

        mid = n // 2
        # 二分分解
        leftList = self.mergeSort(alist[:mid])
        rightList = self.mergeSort(alist[mid:])

        # 合并
        return self._merge(leftList, rightList)


    def _merge(self, leftList, rightList):
        """
        合并操作，将两个有序列表leftList和rightList合并成一个大的有序列表
        """
        l = r = 0
        tempList = []
        while l < len(leftList) and r < len(rightList):
            if leftList[l] <= rightList[r]:
                tempList.append(leftList[l])
                l += 1
            else:
                tempList.append(rightList[r])
                r += 1
            
        tempList += leftList[l:]
        tempList += rightList[r:]
        return tempList

if __name__ == "__main__":
    alist = [6, 5, 3, 1, 4, 7, 2, 4]
    print(alist)
    mergeSort = Sort()
    sortAlist = mergeSort.mergeSort(alist)
    print(sortAlist)

# 结果
[6, 5, 3, 1, 4, 7, 2, 4]
[1, 2, 3, 4, 4, 5, 6, 7]

归并排序复杂度分析，可以写成递推公式：
。为分解成两部分排序的时间复杂度，为合并这两部分已排序数组的时间复杂度。由主定理可求解时间复杂度。

2. 主定理方法

定理

简化记忆：

• 
• 
• 

---

1. 举例一：
   求复杂度。

结果为。

2. 举例二：
   求复杂度。

结果为。

3. 举例三：
   求复杂度。

结果为。

4. 举例四：
   求复杂度。

结果为。

---

3. 斐波那契数|递归树分析法

序列一次为 1，1，2，3，5，8，13，21，......
问题：怎么求出序列中第N个数？

# 递归形式
def fib(n):
    if n <= 1:
        return n
    return fib(n-1)+fib(n-2)

print(fib(5))

# 结果
5

时间复杂度怎么计算？
此时不能套用主定理。使用递归树分析：时间复杂度为。

递归树分析法

空间复杂度如何分析？
递归时有较多的压栈操作。空间复杂度为。

出入栈

斐波那契循环实现：

# 非递归形式
#!/usr/bin/python
def fib(n):
    a = 0
    b = 1
    for i in range(n):
        a, b = b, a + b
    return a

print(fib(5))

# 结果
5

此时的时间复杂度为。

思考：怎么在的时间复杂度下计算fib(n)?
答案：通项公式，。

参考文献

1. Introdution to Algorithem