最近在研究算法,发现其实算法也并不是特别难,只要抓住算法的核心思想,再静下心来,都可以自己实现的。在计算机领域,有一些常见的而且又经常使用的算法,这些算法我们应该掌握,比如常见的排序算法;还有一些算法就是特定领域中经常使用的算法了,这些算法我们只有必须使用时再去学习使用就行了,比如图像处理中的快速傅里叶变换算法。 算法定义 让我们来看看算法的定义吧。(以下定义摘自中文维基百科)
算法的特征 以下是高德纳在他的著作《计算机程序设计艺术》里对算法的特征归纳:
算法的基本要素 算法的核心是创建问题抽象的模型和明确求解目标,之后可以根据具体的问题选择不同的模式和方法完成算法的设计。 说起到算法,那么怎样衡量一个算法的好坏呢?答案是通过两方面来考虑,一是从时间上来考虑,也就是所谓的 时间复杂度
一般来说,计算机算法是问题规模n 的函数f(n),算法的时间复杂度也因此记做 算法执行时间的增长率与f(n) 的增长率正相关,称作渐近时间复杂度(Asymptotic Time Complexity),简称时间复杂度。 常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),…, k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。 空间复杂度
其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。
算法设计的方法 另外,对于算法的设计,通常有以下几种方法。
这些方法在此就不深入讲解了,因为每一个都可以单独拿出长长的一大篇文章来讲解,不过,我后面会继续深入普及这方面的知识的。 算法实现的方法 除了了解到算法的常见设计方法,那么还有哪些常见的实现方法呢。
好了讲了这么多理论,还是用一个例子来解释下算法到底是什么。 求最大公约算法 问题: 求两个自然数的最大公约数 设两个变量M和N 解题步骤: 1.如果M <> 2.M被N除,得到余数R 3.判断R=0,正确则N即为“最大公约数”,否则下一步 4.将N赋值给M,将R赋值给N,重做第一步。 代码实现 void swapi(int *x, int *y) { int tmp = *x; *x = *y; *y = tmp; }int gcd(int m, int n) { int r; do { if (m <> swapi(&m, &n); r = m % n; m = n; n = r; } while (r); return m; } 好了就讲这么多了,如果有什么问题可以在下面评论或者发私信给我。 参考文章
|
|