【数据结构】算法和算法评价

前言

本次文章包括算法、算法的特性、算法效率的度量、算法的计算。

算法定义

算法是对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作。

算法的特性

• 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都在有穷时间内完成。算法必须是有穷的，而程序可以是无穷的。
• 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
• 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
• 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
• 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

“好”算法的特质:

• 正确性
• 可读性
• 健壮性
• 高效率与低存储量需求。

算法效率的度量

时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中基本运算（最深层循环内的语句）的频度与T(n)同数量级，因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。所以算法的时间复杂度为：T(n)=O(f(n))

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。 分析时间复杂性规则：

• 加法规则：T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))，只保留更高阶的项
• 乘法规则：T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))

常见的渐进时间复杂度：常对幂指阶 O(1)<O(log2n)<O(n)<O(n(log2n))<O(n^2 ) <O(n^3) <O(2^n)<O(n!)< O(n^n)

重点

• 顺序执行的代码只会 影响常数项，可以忽略
• 只需挑循环中的一个基本操作分析它的执行次数与n的关系即可
• 如果有多层嵌套循环，只需关注最深层循环循环了几次
• 最好情况：元素n在第一个位置，最好的时间复杂度T(n)=O(1)
• 最坏情况：元素n在最后一个位置，最坏的时间复杂度T(n)=O(n)

三种复杂度

• 最坏时间复杂度：考虑输入数据“最坏”的情况
• 平均时间复杂度：考虑所有输入数据都等概率出现的情况
• 最好时间复杂度：考虑数据输入“最好”的情况

计算方法

1. 找到一个基本操作（最深层循环）
2. 分析该基本操作的执行次数x与问题规模n的关系，x=f(n)
3. x的数量级O(x)就是算法时间复杂度T(n)

空间复杂度

算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模 n的函数，记为 S(n)=O(g(n)) 一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。 算法原地工作：指算法所需的辅助空间为常量，即O(1)

计算方法

普通程序： 1.找到所占空间大小与问题规模相关的变量 2.分析所占空间x与问题规模n的关系，x=f(n) 3.x的数量级O(x)激素算法空间复杂度S(n)

递归程序： 1.找到递归调用的深度x与问题规模n的关系，x=f(n) 2.x的数量级O(x)激素算法空间复杂度S(n) 注意：有的算法各层函数所需存储空间不同，分析方法略有区别

分析空间复杂性规则：

• 加法规则：T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))，只保留更高阶的项
• 乘法规则：T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))

常见的渐进时间复杂度：常对幂指阶 O(1)<O(log2n)<O(n)<O(n(log2n))<O(n^2 ) <O(n^3) <O(2^n)<O(n!)< O(n^n)

---