下载掌阅APP，畅读海量书库
立即打开
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下5个重要的特征。
（1） 有穷性： 一个算法（对任何合法的输入值）必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。
（2） 确定性： 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
（3） 输入： 一个算法有零个或多个输入，以确定运算对象的初始情况。所谓零个输入是指算法本身定出了初始条件。这些输入取自于某个特定对象的集合。
（4） 输出： 一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
（5） 可行性： 一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
算法设计要求正确性、可读性、健壮性、高效率与低存储量需求。
效率指的是算法执行的时间。对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。两者都与问题的规模有关。
算法的复杂性是算法效率的度量，是算法运行所需要的计算机资源的量，是评价算法优劣的重要依据。可以从一个算法的时间复杂度与空间复杂度来评价算法的优劣。当将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素。
（1）硬件的速度。例如，使用486还是使用586。
（2）书写程序的语言。实现语言的级别越高，其执行效率就越低。
（3）编译程序所生成目标代码的质量。对于代码优化较好的编译程序其所生成的程序质量较高。
（4）问题的规模。例如，求100以内的素数与求1 000以内的素数其执行时间必然是不同的。
显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述的各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量大小就只依赖于问题的规模（通常用正整数n表示），或者说它是问题规模的函数。
一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。
一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该操作重复执行的次数作为算法的时间度量。在一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。
许多时候要精确地计算T(n)是困难的，我们引入渐近时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。
定义 （大 Ο 记号）：如果存在两个正常数c和n 0 ，对于所有的n，当n≥n 0 时有：
f(n) ≤ cg(n)
当n＜n0则有：
f(n) = Ο (g(n))
也就是说，随着n的增大，f(n)渐近的不大于g(n)。例如，一个程序的实际执行时间为T(n)=2n 3 +n 2 +5，则T(n)＝ Ο (n 3 )。T(n)和n 3 的值随n的增大渐近地靠拢。
使用大 Ο 记号表示的算法的时间复杂度，称为算法的渐近时间复杂度。
通常用 Ο (1)表示常数计算时间。常见的渐近时间复杂度有：
Ο (1)＜ Ο (log 2 n) ＜ Ο (n) ＜ Ο (nlog 2 n) ＜ Ο (n 2 ) ＜ Ο (n 3 ) ＜ Ο (2 n )
一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。
程序运行所需的存储空间包括以下两部分。
（1）固定部分：这部分空间与所处理数据的大小和个数无关。主要包括程序代码、常量、简单变量和定长成分的结构变量所占的空间。
（2）可变部分：这部分空间大小与算法在某次执行中处理特定数据的大小和规模有关。例如，100个数据元素的排序算法与1 000个数据元素的排序算法所需的存储空间显然是不同的。
算法由数据结构来体现，所以看一个程序首先要搞懂程序实现中所使用的数据结构，如解决装箱问题就使用链表这种数据结构。数据结构是算法的基础，数据结构支持算法，如果数据结构是递归的，算法也可以用递归来实现，如二叉树的遍历。经常采用的算法有迭代法、递推法、递归法、穷举法、贪婪法、分治法和回溯法等，根据考试大纲的要求，对程序员级别的考试，需要考生掌握递归法。