第七期 计算机科学家的算法思维

MidYouth

讲师：李浩然

1. 算法简介

1.1 什么是算法

• 计算机思考、处理信息并解决问题的方式。

1.2 算法的例子

求 498 * 9 的结果
- 498 * 9 = 3600 + 810 + 72 = 4482
- 498 * 9 = 500 * 9 - 2 * 9 = 4482

不同的算法有着不同的效率，但是完成的任务是相同的。

1.3 算法的意义

1. 效率：占用更少的系统资源（内存、CPU、硬盘读写等），从而达到更高的程序运行效率，达到更高的经济效益。
2. 安全：加密算法可以提高网络信息的安全性。
3. 智能：人工智能算法将成为下一步计算机性能发展的一大方向。

2. 基础算法：找到列表中的最大值

ls = [ 81, 94, 92, 71, 98, 87 ]
max = ls[0]
for i in range( 1, len(ls) ):
    if ls[i] > max:
        max = ls[i]

小练习 1

找出如下列表中的最小值：

>>> ls = [ 81, 94, 92, 71, 98, 87 ]

小练习 2

求如下列表所有项的和：

>>> ls = [ 81, 94, 92, 71, 98, 87 ]

如果你有认真听我讲的第五期课程：数据结构，你应该知道以上三个问题都可以分别用一个方法实现。在这里还是希望大家能够将这几个题的算法写出来，从而对算法更加熟悉。

3. 排序算法：将杂乱的一组数据按顺序排列

• 人类的优势：可以通过视觉等感知器官迅速的对周围情况作出判断。
• 计算机的优势：可以将机械重复或者计算量大的任务迅速完成。

3.1 冒泡排序 (Bubble Sort)

• 冒泡排序的基本原理就是，从列表的开头开始，比较临近的两个项。如果前者比后者更大一些，就将两者互换位置。这样的话，每一次遍历整个列表，都会将最大的项推到列表的末尾。

ls = [30, 50, 10, 20, 40]
n = len(ls)
for i in range(n):
    for j in range(0, n-i-1):
        if ls[j] > ls[j + 1]:
            ls[j], ls[j + 1] = ls[j + 1], ls[j] # 两项互换位置

# 在以上的代码中，最后一行代码也可以用另外一种更为常见的方式实现。
            temp = ls[j]
            ls[j] = ls[i]
            ls[i] = temp
# 他们本质上并没有什么区别，只是写法不同而已。

3.2 选择排序 (Selection Sort)

• 选择排序的基本原理就是，在遍历整个列表的时候，记住最小的那个项的索引。每一次遍历完列表，都将找到的最小的那个值放到列表开头，并在下一次遍历的时候不再对已经归类的部分进行遍历。

ls = [30, 50, 10, 20, 40]
n = len(ls)
for i in range(n):
    index_of_min = i
    for j in range(i + 1, n):
        if ls[j] < ls[index_of_min]:
            index_of_min = j
    ls[i], ls[index_of_min] = ls[index_of_min], ls[i]

3.3 时间复杂度

• 时间复杂度是一个用来衡量算法效率的量。当时间复杂度比较高的时候，就说明这个算法将会花费相对较多的时间和系统资源；当时间复杂度低的时候，此算法就将会花费相对较少的时间和系统资源。
• 时间复杂度有很多不同的计算方式。在本节课中，我们将会使用项与项之间的比较次数来衡量时间复杂度。
• 时间复杂度一般用O(n)来表示。

3.3.1 计算冒泡排序的时间复杂度

• 根据上图，我们可以看出，一个长度为 7 的列表，在冒泡排序的过程中，共比较了 6+5+4+3+2+1 = 21 次。
• 假如列表的长度为 n ，则需要比较的次数如下：

  (n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1 
= (n - 1 + 1) + (n - 2 + 2) + (n - 3 + 3) + ... + (n - n + n)
= (n - 1) * n / 2

• 为了简便，我们将分子中的 ’-1’ 删去（反正它对结果的影响也很小），得到O(n) = n^2 / 2

3.3.2 计算选择排序的时间复杂度

• 根据上图，我们可以看出，一个长度为 7 的列表，在选择排序的过程中，共比较了 6+5+4+3+2+1 = 21 次。
• 假如列表的长度为 n，则需要比较的次数如下：

  (n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1 
= (n - 1 + 1) + (n - 2 + 2) + (n - 3 + 3) + ... + (n - n + n)
= (n - 1) * n / 2

• 为了简便，我们将分子中的 ’-1’ 删去（反正它对结果的影响也很小），得到O(n) = n^2 / 2

3.3.3 常见的排序算法的时间复杂度

4. 查找算法：在已经排序好的一个列表里面找出来匹配的值

4.1 直线查找 (Linear Search)

• 直线查找的基本原理就是将整个列表遍历。

ls = [ 10, 20, 30, 40, 50, 60, 70 ]
# 查找数字 50
index = -1
for i in range(len(ls)):
    if ls[i] == 50:
        index = i # 数字 50 在索引 index 上

4.2 二分法查找 (Binary Search)

• 二分法查找的原理就是，将要找的值与中间值对比。如果相等，就找到了。如果要找的值比中间值大，那就用下半部分的列表的中间值进行对比。如果要找的值比中间值小，那就用上半部分的列表的中间值进行对比。这个过程不断重复，最终会找到的。

ls = [10, 20, 30, 40, 50, 60, 70]
low_index = 0
high_index = len(ls) - 1
middle_index = int((low_index + high_index) / 2)
while low_index < high_index:
    if ls[middle_index] > 50:
        high_index = middle_index - 1
        middle_index = int((low_index + high_index)/2)
    elif ls[middle_index] < 50:
        low_index = middle_index + 1
        middle_index = int((low_index + high_index)/2)
    else:
        break
middle_index # 4

5. 课后作业

在这个作业中，我将会给大家提供一个 python 文件，开头是三个长度为一万的列表，格式分别为正序、倒序和随机。请大家写出来一个程序，将这三个列表分别用冒泡排序算法（请写出来）、选择排序算法（请写出来）和归并排序算法（代码会提供）排序，并记录程序运行的时间。

请大家将自己写的代码以及代码的运行结果发给我，然后对结果进行分析。想怎么分析就怎么分析，但是我会打分的哦~