Garland +

Algorithms Divide Conquer Note

Introduction

分治法的基本原理是将原本的问题分成几个较小的问题,然后以递归的方法来解决它们,再把 这些结果结合起来以解决原本的问题。

Karatsuba Multiplication

Merge Sort

问题:有一个含有 N 个元素的随机数列作为输入,我们要把它们从小到大进行排序后输出

归并排序是种递归算法,本质就是把输入数组分成两半,分别对递归的对左右两部分进行排序,然后合并排序好的两部分。关于递归的终止条件,在排序问题中就是输入数组只有0个或者一个元素,那么肯定就是排好序的。

归并排序第一个重要的部分是合并两个已排序的数组

def merge(a, b, n):
    i, j = 0, 0
    c = []
    for _ in range(n):
        if i == len(a):
            c += b[j:]
            break
        if j == len(b):
            c += a[i:]
            break
        if a[i] < b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
    return c

现在来分析下算法的运行时间,直观上看就是执行的操作数量,也就是实际执行的代码行数,先来看下这个合并算法需要的操作步数。

初始化 各自需要一步操作,每一次迭代抛开终止条件的话会进行四次操作,所以整个算法最多需要 次操作(对于上面写的这个应该是 次操作);对于递归的过程,它在不停的回调自身,这个次数是个呈指数级增长的过程,还有一点是每次进行递归调用时, 输入数组是之前大小的一半,所以递归的次数是 次,对于第 次递归,共有 个子问题,每个子问题的输入大小是 ,所以每层递归的调用次数是 ,也就是说不管是第一次递归还是第 次 递归,每次递归的操作数都是 ,然后总共进行的合并的次数是 , 所以归并排序的总操作数是 ,完整的归并排序算法如下:

def merge_sort(array, n):
    pass

Asymptotic Analysis

给了一些简单的例子分析其复杂度,前面几个比较简单就不说了,有一个我觉得比较有意思,一个元素是否存在在一个数组中?

for i=1 to n:
    for j=i+1 to n:
        if A[i] == A[j]: return True
return False

这个的时间复杂度应该是

Blog

Thoughts

Project