算法的特性
文老师软考教育
◆算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列,其中每一条指令表示一个或多个操作。此外，一个算法还具有下列5个重要特性。（1）有穷性。一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束,且每一步都可在有穷时间内完成。
（2）确定性。算法中的每一条指令必须有确切的含义，理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
（3）可行性。一个算法是可行的，即算法中描述的操作都可以通过已经实现的基
本运算执行有限次来实现。
（4）输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
（5）输出。一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的
2
算法的复杂度
文老师软考教育
◆算法的时间复杂度分析：主要是分析算法的运行时间，即算法执行所需要的基本操作数。不同规模的输入所需要的基本操作数是不相同。在算法分析中.可以建立以输入规模n为自变量的函数T(n)来表示算法的时间复杂度。
◆即使对于相同的输入规模，数据分布不相同也影响了算法执行路径的不同，因此所需要的执行时间也不同。根据不同的输入，将算法的时间复杂度分析分为3 种情况：最佳情况、最坏情况、平均情况。
◆渐进符号：以输入规模n为自变量建立的时间复杂度实际上还是较复杂的，例如an2+bn+c，不仅与输入规模有关，还与系数a、b和c有关。此时可以对该函数做进一步的抽象，仅考虑运行时间的增长率或称为增长的量级，如忽略上式中的低阶项和高阶项的系数，仅考虑n^2。当输入规模大到只有与运行时间的增长量级有关时，就是在研究算法的渐进效率。也就是说，从极限角度看，只关心算法运行时间如何随着输入规模的无限增长而增长。下面简单介绍3种常用的标准方法来简化算法的渐进分析。
算法的复杂度
文老师软考教育
◆算法的时间复杂度分析：主要是分析算法的运行时间，即算法执行所需要的基本操作数。不同规模的输入所需要的基本操作数是不相同。在算法分析中，可以建立以输入规模n为自变量的函数T(n）来表示算法的时间复杂度。
◆即使对于相同的输入规模，数据分布不相同也影响了算法执行路径的不同,因此所需要的执行时间也不同。根据不同的输入，将算法的时间复杂度分析分为3种情况：最佳情况、最坏情况、平均情况。
◆渐进符号：以输入规模n为自变量建立的时间复杂度实际上还是较复杂的，例如an2+bn+c，不仅与输入规模有关，还与系数a、b和c有关。此时可以对该函数做进一步的抽象，仅考虑运行时间的增长率或称为增长的量级，如忽略上式中的低阶项和高阶项的系数，仅考虑n^2。当输入规模大到只有与运行时间的增长量级有关时，就是在研究算法的渐进效率。也就是说，从极限角度看，只关心算法运行时间如何随着输入规模的无限增长而增长。下面简单介绍3种常用的标准方法来简化算法的渐进分析。
2
文老师软考教育
算法的复杂度
（1)0记号。定义为：给定一个函数g(n)，O(g(n))={f(n)：存在正常数c和nO，使得对所有的n≥no，有0≤f(n)≤g(n)}，如图（a）所示。0(g(n))表示一个函数集合，往往用该记号给出一个算法运行时间的渐进上界。考试中一般只涉及到0符号。（2）Q记号。定义为：给定一个函数g(n)，Q(g(n))={f(n):存在正常数c和nO，使得对所有的n≥no，有0≤g(n)sf(n)]，如图（b）所示。Q(g(n））表示一个函数集合，往往用该记号给出一个算法运行时间的渐进下界。
（3）日记号。定义为：给定一个函数g(n)，O(g(n))=[f(n)：存在正常数c1，、c2和no，使得对所有的n≥n0。，有0≤c1g(n)≤f(n)≤c2g(nJ]}，如图（c）所示。θ(g(n))表示一个函数集合，往往用该记号给出一个算法运行时间的渐进上思和渐进下史即渐进紧致界。