欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

演算法 - 算法与算法分析

程序员文章站 2024-03-16 21:07:52
...

一,算法

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 演算法初学)

相关标签: 演算法