引入
最大公约数求解
求两个不全为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$$ ,使得 $$\forall n > n_0,t(n) \leqslant cg(n)$$,我们称函 数 $$t(n)$$ 包含在 $$O(g(n))$$ 中,记作 $$t(n)\in O(g(n))$$。
下界$$\Omega$$的定义
如果存在大于0的常数c和非负整数$$n_0$$,使得$$\forall n > n_0$$,$$t(n) > cg(n)$$,我们称函数 $$t(n) $$ 包含在 $$\Omega(g(n))$$ 中,记作 $$t(n) \in \Omega(g(n))$$。
$$\theta$$的定义
若存在大于0的常数$$c1,c2$$和非负整数$$n_0,\forall n > n_0,c_1g(n) \leqslant t(n) \leqslant c_2g(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^2_n $$
$$ C_{worst}(n)=C^2_n $$
$$ C_{avg}(n)=C^2_n $$
$$ \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^2_n $$
$$ C_{worst}(n)=C^2_n $$
$$ C_{avg}(n)=C^2_n \in \theta(n^2) $$
基本效率类型
$$ 1<log_n<n<nlog_n<n^2<n^3<2^n<n! $$