02 - Algorithm Design

02 - 算法设计

1. 搜索算法

1.1. 线性搜索

也是一个例子。线性搜索的复杂度为参数n

1.2. 二分查找

如果我们事先直到一些信息，比如：数组是有序的，那么搜索的复杂度降低为log2n

2. 排序算法

2.1. 冒泡排序

嵌套循环实现。

每次把最大的数字换到最后...这样得到一个从小到大的有序数组。复杂度O(n^2)

2.2. 选择排序

每次把最小的和他的正确位置进行交换。

2.3. 算法的复杂度 - Big O Notation

因为收到计算机硬件的影响，可以去除一些微小的影响。取最高阶数，去除常数。学过再回来听会感觉很好！感觉我第一次听也会很懵逼啊。

3. 递归

recursive case。基本的是函数的递归，通过递归来实现整数的平方。

3.1. 归并排序

分治策略：大数据背景下优于冒泡排序

将一个长序列分解为两个短序列分别排序。

1. 分解：将当前序列分成两个长度相等的子序列。

2. 递归：对这两个子序列分别进行归并排序。

3. 1. sort left half

   2. sort right half

4. 合并：将两个有序的子序列合并成一个有序的序列。

• • merge the halves

3.2. 动态内存区

递归引出的堆栈，可能引发灾难。

4. 穿插

通过邮件引入网站的介绍...HTML...这个引入就够国内的教学琢磨50年。

进一步介绍了密码学的内容：上节课有提及的

• secret-key crypto

密文 - 密钥

4.1. 又请吃饭...

哈佛真有米啊..上个课周周团建的...

4.2. CS50 居然火爆到出文创了

牛逼！