什么是算法?其本质特征是什么?如何理解算法的能行性?
算法的定义 ?
算法(Algorithm)是一系列解决问题的清晰指令,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
? 算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列,并且这样的步骤和序列可以解决一类问题。
? 一个算法应该具有以下五个重要的特征:
? 1、有穷性: 一个算法必须保证执行有限步之后结束;
? 2、确切性: 算法的每一步骤必须有确切的定义;
? 3、输入:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定除了初始条件;
? 4、输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。
没有输出的算法是毫无意义的;
? ?5、可行性: 算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。 ? 计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》,可见算法在计算机科学界与计算机应用界的地位。
[编辑本段]算法的复杂度 ? 同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 ? 时间复杂度 ? 算法的时间复杂度是指算法需要消耗的时间资源。
一般来说,计算机算法是问题规模n 的函数f(n),算法的时间复杂度也因此记做 ? T(n)=Ο(f(n)) ? 因此,问题的规模n 越大,算法执行的时间的增长率与f(n) 的增长率正相关,称作渐进时间复杂度。
? 空间复杂度
?算法的空间复杂度是指算法需要消耗的空间资源。
其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。
算法设计与分析的基本方法 ?
1。递推: ? 递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。
它把问题分成若干步,找出相邻几步的关系,从而达到目的,此方法称为递推法。
2。递归: ? 递归指的是一个过程:函数不断引用自身,直到引用的对象已知
3。穷举: ? 穷举是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。
4。贪婪: ? 贪婪法是一种不追求最优解,只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯。
? 5。分治: ? 把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
6。动态规划: ? 动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。
其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础,被广泛应用于计算机科学和工程领域。
?7。迭代: ? 迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题(一般是解方程或者方程组)的过程,为实现这一过程所使用的方法统称为迭代法。
算法分类 ?
可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法。 ?
算法可以宏泛的分为三类: ?
有限的、确定性算法 。
这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务,但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。 然而,对于一个(或一些)给定的数值,算法的结果并不是唯一的或确定的。
无限的算法 是那些由于没有定义终止定义条件,或定义的条件无法由输入的数据满足而不终止运行的算法。
通常,无限算法的产生是由于未能确定的定义终止条件。
从集合A到集合B的一个映射
答:详情>>
答:教育的精神是人的自由、平等、健康、和谐的发展。详情>>
答:教育的基本目的和任务就在于授业、释疑和解惑,也就是对人类各种已有知识的诠释和传授。你明白了这一点,也就明白了教育与诠释学之间的内在联系了。详情>>
答:贺拉斯 认为文学的摹仿要达到“既劝谕读者,又使他喜爱,才能符合众望”。这是一种既重视摹仿又重视读者得到快感和教益的文学观念。详情>>