
。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算
明确性:算法的描述必须无歧义,以保证算法的实际执行结果是精确地符合要求或期望,通常要求实际运行结果是确定的。
只有有限个状态、有限个输入符号和有限个转移函数(指令)。而一些定义更规定算法必须在有限个步骤内完成任务。
有效性:又称可行性。能够实现,算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。
算法的核心是创建问题抽象的模型和明确求解目标,之后可以根据具体的问题选择不同的模式和方法完成算法的设计。
和不完全遍历法:在问题的解是有限离散解空间,且可以验证正确性和最优性时,最简单的算法就是把解空间的所有元素完全遍历一遍,逐个检测元素是否是我们要的解。这是最直接的算法,实现往往最简单。但是当解空间特别庞大时,这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。
分治法:把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。
法:当问题的整体最优解就是由局部最优解组成的时候,经常采用的一种方法。
:常见的近似求解思路。当问题的整体最优解不是(或无法证明是)由局部最优解组成,且对解的最优性没有要求的时候,可以采用的一种方法。
简并法:把一个问题通过逻辑或数学推理,简化成与之等价或者近似的、相对简单的模型,进而求解的方法。
算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务,如计算职工的薪水或打印学生的成绩单。一般地,当算法在处理信息时,会从
是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模n的函数f(n),算法的时间复杂度也因此记做
算法执行时间的增长率与f(n)的增长率正相关,称作渐近时间复杂度,简称时间复杂度。
常见的时间复杂度有:常数阶O(1),对数阶,线性阶 O(n),线性对数阶,平方阶,立方阶,...,k次方阶,指数阶。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低
是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。
。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小,可以将下面的算法形象地称为“捡豆子”:
从第二颗豆子开始检查,如果正在检查的豆子比口袋中的还大,则将它捡起放入口袋中,同时丢掉原先口袋中的豆子。反之则继续下一颗豆子。直到最后一颗豆子。
以上算法在中国大陆的教科书中通常被叫做“打擂法”或者“循环打擂”:在一个for循环中,每轮循环都有新的挑战者。若挑战者胜的话,挑战者做新擂主,否则擂主卫冕。for循环结束后输出最后的擂主。
int max(int *array, int size){ int mval = *array; int i; for (i = 1; i size; i++) if (array[i] mval) mval = array[i]; return mval;}
设两个变量{\displaystyle M}和{\displaystyle N}
如果{\displaystyle MN},则交换{\displaystyle M}和{\displaystyle N}
{\displaystyle M}被{\displaystyle N}除,得到余数{\displaystyle R}
判断{\displaystyle R=0},正确则{\displ谈球吧aystyle N}即为“最大公约数”,否则下一步
将{\displaystyle N}赋值给{\displaystyle M},将{\displaystyle R}赋值给{\displaystyle N},重做第一步。
//交换2数void swapi(int *x, int *y){ int tmp = *x; *x = *y; *y = tmp;}int gcd(int m, int n){ int r; do { if (m n) swapi(&m, r = m % n; m = n; n = r; } while (r); return m;}
利用if函数以及递归则能做出更为精简的代码,更可省去交换的麻烦。(但是也因为递归调用,其空间复杂度提高)
int gcd(int a,int b){ if(a%b) return gcd(b,a%b); return b;}
刘波, 王凌, 金以慧. 差分进化算法研究进展[J]. 控制与决策, 2007, 22(7):721-729.
