lec 18 Asymptotics II

CS61B

NOTE: 判断时间复杂度的时候，最好写一些例子，不要只看几个for循环就下结论，还可以画图：

For Loop:

题目：

策略：

题目：

Recursion:

右边的图给了很多hint, 比如我按return 1被执行的次数计算,就很简单：

Binary Search

数量每变为原来的两倍，其实logN只是变化了一点点。形象一点的比喻就好像在翻一个电话簿，用户数量扩大为原来的两倍，但增加的时间只是第一步确定要查找的是在哪一半这么一丢丢时间：

Merge Sort

先介绍了selection sort,就是一遍一遍地遍历整个数组比较大小，需要比较n+n-1+n-2+....+2+1次：

当使用merge sort时，如果每一部分都是sorted,那么下面的merge sort需要N次comparison：

尝试一种可以减少比较次数的方法，把所有数组元素分成两部分，每一部分分别用selection sort排序，最后再把两部分用merge sort合并：

发现规律，每一层如果都是最后用merge sort排序的，都需要N次comparison，而这个层数可以用logN计算出来：

一直分到最后每组只有一个元素也就是sorted,最后再merge,每层需要N次，一共logN层：

很棒的短片教程：

Merge Sort

最后要注意一下NlogN跟N其实很接近，logN是相对来说很小的数：

Asymptotics II Study Guide

简介：

分析runtime要深度思考，不能简单机械地处理。比如看到两个for loops就觉得是Θ（N²）可能是错误的！

要会选择cost model, 选择程序中的一个操作然后来计算他们发生的次数；

两个重要的总数（中国小学生数学水平）