Merge Sort
该课程前面几节课作为入门, 所以会介绍一些算法, 但后面会有更扎实、底层诸如复杂度分析等内容.
按讲者说法, 这种算法还是比较实际引用广泛的, 我后来稍微google了一下, 说这种算法最坏最好情况都是一样的时间复杂度.
思想很简单, 属于Divide and Conquer , 就是递归的把它二分打散, 再用O(N)的函数把它们merge起来. 下面的代码是不去重的, 即有重复数字仍然包含在内.
def merge_sorted_lists(a, b):
res = []
# init indices for a, b
i = 0
j = 0
while i < len(a) and j < len(b):
if a[i] < b[j]:
res.append(a[i])
i = i + 1
else:
res.append(b[j])
j = j + 1
if i < len(a):
res = res + a[i:]
else:
res = res + b[j:]
return res
def merge_sort(l):
# THIS IS for exit!!!
if len(l) <= 1:
return l
a = l[:int(len(l)/2)]
b = l[int(len(l)/2):]
left = merge_sort(a)
right = merge_sort(b)
return merge_sorted_lists(left, right)
if __name__ == '__main__':
l = [4,5,7,9,7,5,1,0,7,-2,3,-99,6]
print(merge_sort(l))
在度量其复杂度时, 讲者采用的是recursive tree, 其实就是笨办法, 把递归过程全部列出来, 计算每一层级需要的代价. 在第j (j=0,1,2,...,logN)层, 有2^j子问题(就是需要merge的)， 每个子问题的size是(至多)需要6(N/(2^j))的代价(代码行数). 因此, 不管在哪一层, 代价都是6N, 所以最多就是6N(1+logN).
