算法和算法分析

一个问题抽象为一个抽象数据类型后，仅是形式上的抽象定义，还没有达到问题解决的目的，要实现这个目标，就要吧抽象的变成具体的，即抽象数据类型再计算机上实现，变为一个能用的具体的数据类型！? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

算法和算法分析

算法的定义：

????????对特定的问题求解方法和步骤的一种描述，它是指令的有限序列，某种每个指令表示一个或多个操作（简而言之，算法就是解决问题的方法和步骤）；

算法与程序 ：

? ? ? ? 算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出；一个问题可以有多种算法，程序是用某种程序设计语言对算法的具体实现：

? ? ? ? 程序=数据结构+算法

? ? ? ? 数据结构通过算法实现操作

? ? ? ? 算法根据数据结构设计程序

算法的特性：

? ? ? ? 一个算法必须具备以下五个重要特性

• ? ? ? ? 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时完成；
• ? ? ? ? 确定性：算法中的每一条指令必须有确定的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出；
• ? ? ? ?可行性：算法是可执行的，算法描述的操作可以通过正经实现的基本操作执行有限次来实现；
• ? ? ? ?输入：一个算法要有零个或多个输入；
• ? ? ? ?输出：一个算法要有一个或多个输出；

算法的设计要求：??

????????1.正确性：程序对于精心选择的、典型的苛刻且带有刁难性的几组输入数据且能够得出满足需求的结果！

? ? ? ? 2.可读性：算法主要是为了人的阅读与交流，要具有易于人的理解；

? ? ? ? 3.健壮性：指当输入非法数据时，算法恰当的做出反应或进行相应处理，而不是产生莫名其的输出结果；

? ? ? ? 4.高效性：要求花费尽量少的时间和尽量低的存储需求；

算法分析 ：

? ? ? ? 一个好的算法首先要具有正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率的高低来评价不同算法的优劣程序；

算法的效率通过以下两种方面来考虑：

? ? ? ? 1.时间效率：指的是算法所消耗的时间！

? ? ? ? 2.空间效率：指的是算法执行过程中所消耗的存储空间！

? ? ? ? 注：时间效率与空间效率有时候是矛盾的！

算法时间效率的度量：?

? ? ? ? ?可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量；

两种度量方法：

? ? ? ? 1.事后统计：将算法实现，测算其时间和空间开销；

? ? ? ? 2.事前分析：对算法所消耗资源的一种估算方法；

事前分析方法：一个算法的运行时间是指一个算法在计算机上运行所消耗的时间大致可以等于计算机执行一种简单的操作（如赋值、比较、移动等）所需的时间与算法中进行的简单操作次数乘积；

? ? ? ? 算法运行时间=一个简单操作所需的时间?简单操作的次数?

也即算法中每条语句的执行时间之后：

? ? ? ? 算法运行时间=每条语句的执行次数（又称为语句的频率）?该语句执行一次所需的时间

若有某个辅助函数f（n），使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f（n）是T（n）的同数量级函数，记作T（n）=O（f（n）），称O（f（n））为算法的渐进时间复杂度（O是数量级的符号）简称时间复杂度！

n越大算法执行时间越长：

? ? ? ? 排序：n为记录数；

? ? ? ? 矩阵：n为矩阵的阶数；

? ? ? ? 多项式：n为多项式的项数；

? ? ? ? 集合：n为元素的个数；

? ? ? ? 树：n为树的结点个数；

? ? ? ? 图：n为图的顶点数或边数；?