09. 算法概述

最大公约数求解

求两个不全为 0 的非负整数（m 和 n）的最大公约数（记作 gcd(m, n)）。

中学的计算方法

• 找到 m 的所有质因数；
• 找到 n 的所有质因数；
• 找出所有的公因数；
• 将找到的公因数相乘，结果即为最大公约数；

60 = 2*2*3*5
24 = 2*2*2*3
gcd(60, 24) = 2*2*3 = 12

欧几里得算法

• 如果 n = 0，返回 m 的值作为结果，过程结束；否则，进入第二步；
• m 除以 n，得到余数 r；
• 将 n 的值赋给 m，将 r 的值赋给 n，返回第一步；

gcd(60, 24) = gcd(24, 60 mod 24) = gcd(24, 12)
			= gcd(12, 24 mod 12) = gcd(12, 0) = 12

# 欧几里得算法伪代码
def Euclid(m, n):
    while n != 0:
        r = m mod n
        m = n
        n = r
    return m

连续整数检测法

• 将 min(m, n)的值赋给 t；
• m 除以 t，如果余数为 0，进入第 3 步，否则进入第 4 步；
• n 除以 t，如果余数为 0，返回 t 的值，否则进入第 4 步；
• 将 t 的值减 1，返回第 2 步；

# TODO

算法的定义

• 数学：

  算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。

• 广义：

  • 算法是完成某项工作的方法和步骤：
    • 菜谱是做菜的算法；
    • 歌谱是一首歌曲的算法；

• 计算机科学

  算法是解决问题的一系列明确指令，也就是说，对于符合一定规范的输入，能够在有限时间内获得要求的输出。

算法的特点

• 明确性
• 有限性
• 一般性
• 有序性
• 不唯一性

常见问题

排序

选择排序

扫描整个列表，找到最小元素，和第 1 个元素交换；然后从第 2 个元素开始扫描列表，找到后面 n − 1 个元素的最小值，和第 2 个元素交换位置；如此重复。

'''
输入: 一个杂乱的数据 A[0...n − 1]
输出: 升序排列的数据 A[0...n − 1]
'''
function Selection_Sort(A[0...n − 1])
    for i = (0 , n − 2) do
        min = i //min 为最小元素索引
        for j = (i + 1 , n − 1) do
            if A[j] < A[min] then
                min = j
            end if
        end for
        swap A[i] and A[min]
    end for
end function

冒泡排序

比较相邻元素，如果它们逆序就交换它们的位置，重复多次以后最大的元素就放置到最后的位置；如此放置次大的元素至倒数第 2 个位置；重复此过程。

'''
输入: 一个杂乱的数据 A[0...n − 1]
输出: 升序排列的数据 A[0...n − 1]
'''
function Bubble_Sort(A[0...n − 1])
    for i = (0 , n − 2) do
        for j = (0 , n − 2 − i) do
            if A[j + 1] < A[j] then
                swap A[j] and A[j + 1]
            end if
        end for
    end for
end function

查找

顺序查找

折半查找

字符串处理

蛮力匹配

图

拓扑排序

地图四染色

旅行商问题

组合问题

背包问题

分配问题

最近对问题

几何问题

凸包问题

数值问题

整数相乘

算法效率分析

输入规模：几乎所有的算法，运行时间都随着输入规模的增大而增大

渐进符号

上界$O$的定义

如果存在大于 0 的常数 $c$ 和非负整数 $n_0$ ，使得 $\mathrm{\forall }n>n_0，t(n)⩽cg(n)$，我们称函 数 $t(n)$ 包含在 $O(g(n))$ 中，记作 $t(n)\in O(g(n))$。

下界$\mathrm{\Omega }$的定义

如果存在大于 0 的常数 c 和非负整数$n_0$，使得$\mathrm{\forall }n>n_0$，$t(n)>cg(n)$，我们称函数 $t(n) $ 包含在 $\mathrm{\Omega }(g(n))$ 中，记作 $t(n)\in \mathrm{\Omega }(g(n))$。

$\theta$的定义

若存在大于 0 的常数$c1,c2$和非负整数$n_0,\mathrm{\forall }n>n_0,c_{1}g(n)⩽t(n)⩽c_{2}g(n)$,我们称函数 t(n)包含在 $\theta (g(n))$ 中，记作 $t(n)\in \theta (g(n))$。

算法的三种效率

• 最差效率$C_{worst}(n)$：输入规模为 n 时，算法在最坏输入下的效率；
• 最优效率$C_{best}(n)$：输入规模为 n 时，算法在最好输入下的效率；
• 平均效率$C_{avg}(n)$：输入规模为 n 时，算法在随机输入下的效率；

选择排序算法效率分析

'''
输入: 一个杂乱的数据 A[0...n − 1]
输出: 升序排列的数据 A[0...n − 1]
'''
function Selection_Sort(A[0...n − 1])
    for i = (0 , n − 2) do
        min = i //min 为最小元素索引
        for j = (i + 1 , n − 1) do
            if A[j] < A[min] then
                min = j
            end if
        end for
        swap A[i] and A[min]
    end for
end function

$$C_{best}(n)=C_n^2$$$$C_{worst}(n)=C_n^2$$$$C_{avg}(n)=C_n^2$$$$\frac{1}{2}n(n-1)\in \theta (n^2)$$

冒泡排序算法效率分析

'''
输入: 一个杂乱的数据 A[0...n − 1]
输出: 升序排列的数据 A[0...n − 1]
'''
function Bubble_Sort(A[0...n − 1])
    for i = (0 , n − 2) do
        for j = (0 , n − 2 − i) do
            if A[j + 1] < A[j] then
                swap A[j] and A[j + 1]
            end if
        end for
    end for
end function

$$C_{best}(n)=C_n^2$$$$C_{worst}(n)=C_n^2$$$$C_{avg}(n)=C_n^2\in \theta (n^2)$$

基本效率类型

$$1<lo{g}_n<n<nlo{g}_n<n^2<n^3<2^n<n!$$