算法的五个重要特征:
1、输入:一个算法有零个或多个输入,描述运算对象的初始情况。 例如,jldy算法有两个输入: m和n。
2、确定性:算法的各个步骤必须正确定义。 也就是说,算法中必须严格且含混地规定应该执行的所有动作,不能有模糊性。 例如,在jldy算法中,在步骤1中,“m除以n”。 但是,不能有用m除n或用m除n这两种可能的做法的规定。
3、有穷性:一个算法在执行上有穷,有落后就要结束。 也就是说,算法中包含的计算步骤有限。 例如,在jldy算法中,m和n都是正整数,步骤1后,r一定小于n,如果r不等于0,则下一次进行步骤1时,n的值减少,正整数的降序序列一定结束。 因此,无论给定的m和n的原始值多么大,步骤1的执行都是贫穷的。
4、输出:算法有一个或多个输出。 也就是说,与输入有某种特定关系的量,简单来说就是算法的最终结果。 例如,jldy算法只有一个输出,即步骤2中的n。
5、可行性:算法需要执行的运算和操作必须是相当基本的。 换言之,他们可以准确进行,算法的执行者甚至不需要掌握算法的含义,而是根据该算法各步骤的要求进行操作,最终得到正确的结果。
算法的复杂性
1 .时间复杂度:算法的时间复杂度是指算法消耗的时间资源。
2 .空间复杂度:算法的空间复杂度是指算法消耗的空间资源。 其计算和显示方法与时间复杂度相似,一般用复杂度的渐近性表示。
1、用自然语言描述算法
上述的jldy算法以及算法实例的记述都使用自然语言。 自然语言是指人们日常使用的语言,如中文、英语、德语等。 使用这些语言不需要特别的训练,所描述的算法也很容易理解。
2、用流程图描述算法
在数学课上,我学习了用程序框图描述算法。 在程序的框图中,流程图是描述算法的常用工具,用几个图形符号表示算法。
3、用伪码描述算法
伪代码是一种用介于自然语言和计算机语言之间的字符和符号描述算法的工具。 由于不使用图形符号,所以书写方便、结构紧凑、容易理解,容易过度访问计算机编程语言。
基本方法
1 .推法
推送法是利用问题本身所具有的递归关系来求解问题的方法。 它把问题分成几个步骤,找出相邻步骤的关系,从而达到目的。 这个方法被称为推送法。
2 .递归法
递归是函数在知道要引用的对象之前持续引用自身的过程
3 .穷举搜索法
穷举检索法是指按照某种顺序列举并验证可能是解的多个解候补,从大众那里找出符合这些要求的解候补作为问题的解。
4 .贪婪法
贪婪法是不追求最优解,而寻求更满意解的方法。 贪婪法一般能迅速得到满意的解。 那是因为,为了寻找最佳解,将省去为了尽可能地网罗而必须花费的大量时间。 贪婪法总是根据现在的情况做出最佳选择,不考虑各种可能的整体情况,所以贪婪法不要倒退。
5 .分治法
分割统治法是指将一个复杂的问题分成两个以上相同或类似的子问题,再将子问题分成更小的子问题……直到最后子问题才可以简单地直接求解,是原问题的解,即子问题的解的综合。
6 .动态规划法
动态规划是解决数学和计算机科学中使用的包括重叠部分问题的优化问题的方法。 其基本想法是将原题分解为相似的子题,在求解的过程中从子题的解中求得原题的解。 动态规划的思想是多种算法的基础在计算机科学和工程领域有着广泛的应用
7 .迭代法
迭代法是指在数值分析中,通过从一个初始估计中寻找一系列近似解来求解问题(一般为方程或方程)的过程,用于实现这一过程的方法统称为迭代法。
8 .分支边界法
与贪婪算法一样,该方法也是用于设计组合优化问题的求解算法,但在搜索问题的整个可能解空间方面有所不同。 虽然所设计的算法比贪婪算法的时间复杂度高,但其优点是与穷举法一样能够可靠地求出问题的最优解。 另外,该方法不是盲目的穷举搜索,在搜索中通过极限,可以中途停止对得不到最优解的部分空间的进一步搜索(