演算法 - 算法与算法分析
文章目录
一,算法
1,算法的定义
- 对特定问题求解方法和步骤的一种描述,他是指令的有限序列。其中每个指令表示一个或多个操作。
2,算法的描述
- 自然语言:英语,中文
- 流程图:传统流程图,NS流程图
- 伪代码(类语言):类C语言
3,算法与程序
- 算法是解决问题的一种方法或一个过程,考虑如何将输入转换为输出,一个问题可以拥有多种算法。
-
程序是用某种程序设计语言对算法的具体实现。
程序 = 数据结构 + 算法
– 数据结构通过算法实现操作
– 算法根据数据结构设计程序
4,算法的五大特性
-
有穷性
一个算法必须总是在执行有穷步骤之后结束,且每一步都在有穷时间内完成。 -
确定性
算法中每一条指令必须有确切含义,没有二义性,在任何条件下,只有唯一的一条执行路径,即对于相同输入只能得到相同输出。 -
可行性
算法是可执行的,算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 -
输入
有零个或多个输入。 -
输出
有零个或多个输出。
5,算法的设计要求
- 正确性(Correctness)
– 对于精心选择的、典型的、苛刻且带有刁难性的几组输入数据均能的出满足要求的结果 - 可读性(Readability)
– 易于人的理解 - 健壮性(Robustness)
– 当输入非法数据时,做出且当反应 - 高效性(Efficiency)
– 花费时间小,尽量低的存储需求
二,渐进表示法(Asymptotic notation)
五种渐进表示方法
L:洛必达法则((L’ Hospital Rule)
渐进表示法的定义
asymptotic tight bound:渐近紧密界
Big-O(Upper bound of f(n))
以定义来说明范例
Omega(Lower bound of f(n))
以定义来说明范例
Theta (tight bound)
以定义来说明范例
Small-O
Small-Omega
1,渐进表示法的性质
-
传递性(Transitivity)
-
自反性(Reflexivity)
-
对称性(Symmetry)
-
转置对称(Transpose symmetry)
2,标准符号与通用函数
(Standard notations and Common functions)
- 单调性(Monotonicity)
A function f is monotonically increasing if m ≤ n implies f(m) ≤ f(n).
加粗位置符号,可以使≥,≤,>,<,但前后必须同号 - 取下整和取上整(Floor and Ceiling)
-
模运算(Modular arithmetic)— 取余数
例:7 mod 2 = 7 - 3*2 = 1
- 多项式与指数率(Polynomials v.s. Exponentials)
- 对数(Logarithms)
- 阶乘(Factorials) — 斯普林斯近似
- 函数迭代(Function iteration)
- 迭代对数函数(The iterative logarithm function)
三,算法分析
首先满足四个设计要求,在考虑算法的效率,通过效率的高低来判断不同算法的优劣。
算法效率以下两个方面来考虑:
- 时间效率:指算法所耗费的时间;
- 空间效率:指算法执行过程中所耗费的存储空间。
时间效率和空间效率有时候是矛盾的。
1,算法时间效率的度量
可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量。
两种度量方法:
- 事后统计
– 将算法实现,测算其时间和空间的开销。
– 缺点:表写程序花费时间多;所得结果依赖于计算机软硬件等环境因素。 - 事前分析(更优)
– 对算法所消耗资源的一种估算。
事前分析方法
- 算法运行时间 = 一个简单操作所需时间 * 简单操作次数
- 即是:
算法运行时间 = Σ(语句频度 *该语句执行一次所需时间)
语句频度:每条语句的执行次数
该语句执行一次所需时间:时间结果依赖于计算机软硬件等环境因素,所以假设执行每一条语句执行一次所需时间均为单位时间 - 最终使用结果:
算法运行时间 = Σ 语句频度
讨论该算法中所有语句的执行次数之和,即频度之和。
例如:两个 n x n矩阵相乘算法可描述为:
我们把算法所消耗的时间定义为该算法中所有语句的执行次数之和,则上述算法的时间消耗为:
- T(n) = 2n3 + 3n2 +2n + 1
2,渐进时间复杂度 – O(n)
算法时间复杂度定义
算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作:T(n) = O(f(n))
它表示随着n的增大,算法执行的时间的增长率和f(n)的增长率相同,称渐进时间复杂度。
为了便于比较不同算法的时间效率,我们比较他们的数量级(Order)
例如:两个不同的算法,时间消耗分别为:(T1更优)
T1(n) = 10n2 与 T2(n) = 5n3
若有某个辅助函数 f(n),使得当 n 趋近于无穷大时,T(n) / f(n) 的值为不等于零的常数,则称 f(n) 是 T(n)的同数量级函数。记作 T(n) = O(f(n)),称 O(f(n)) 为算法的渐进时间复杂度(O是数量级的符号),简称时间复杂度。
举个“栗子”:
对于求解矩阵相乘问题,所耗费的时间:T(n) = 2n3 + 3n2 +2n + 1
当 n → ∞时,T(n) / n3 → 2,则表示n充分打时 T(n) 与 n3 是同阶或同数量级的,引入 “O”记号,则 T(n)可记作:
- T(n) = O(n3) — 算法的渐进时间复杂度
一般情况下,不必计算所有操作的执行次数,而只是考虑算法中的基本操作执行次数,他是问题规模n的某个函数,用T(n)表示。
再举个比较难的“栗子”
分析下程序时间复杂度
i = 1 # 语句1
while i <= n:
i = i * 2 # 语句2
若循环执行1次:i = 1 * 2 = 2,
若循环执行2次:i = 2 * 2 = 22,
若循环执行3次:i = 2 * 2 * 2 = 23, … ,
若循环执行x次:i = 2x
设语句2执行数为x次,有循环条件 i <= n,
∴ 2x <= n
∴ x <= log2n
2f(n) <= n
即f(n) <= log2n,取最大值f(n) = log2n
所以该程序段时间复杂度T(n) = O(log2n)
注意:有的情况下,算法中基本操作重复执行的次数还随问题的输入数据集不同而不同
例:顺序查找法,在list中找到数值为e的元素
for i in input_list:
if i == e:
print(f'{e} at {input_list.index(i)}'
break
最好情况:1次
最坏情况:n
平均时间复杂度:O(n)
- 最坏时间复杂度:指在最坏情况下,算法时间复杂度
- 平均时间复杂度:指所有可能输入实例在等概率出现情况下,算法的期望运行时间
- 最好时间复杂度:指在最好情况下,算法时间复杂度
一般考虑在最坏情况下的时间复杂度,以保证算法的运行时间不会比他长。
对于复杂的算法,可以将他分成几个容易估算的部分,然后利用加法规则和乘法规则,计算算法时间复杂度:
3,渐进空间复杂度 – S(n)
空间复杂度:算法所需存储空间的度量,
- 记作:S(n) = O(f(n)),其中n为问题的规模(或大小)
算法要占用的空间
- 算法本身占据的空间,输入和输出,指令,常数,变数等
- 算法需要使用的辅助空间
例:将一个一位数组a中的n个数逆序存放在原数组中。
算法一:S(n) = O(1) — 只需要一个辅助空间key
n = len(a)
for i in range(n / 2):
key = a[i]
a[i] = a[n - i - 1]
a[n - i - 1] = key
算法二:S(n) = O(n) — 需要一个长度为n的辅助列表b
n = len(a)
b = [0] * n
for i in a:
b[n - i - 1] = i
for j in range(n):
a[j] = b[j]
(2020年3月31日20:00:20 演算法初学)