算法入门

最近在研究算法，发现其实算法也并不是特别难，只要抓住算法的核心思想，再静下心来，都可以自己实现的。在计算机领域，有一些常见的而且又经常使用的算法，这些算法我们应该掌握，比如常见的排序算法；还有一些算法就是特定领域中经常使用的算法了，这些算法我们只有必须使用时再去学习使用就行了，比如图像处理中的快速傅里叶变换算法。

算法定义

让我们来看看算法的定义吧。（以下定义摘自中文维基百科）

在数学和计算机科学/算学之中，算法/演算法/算则法（Algorithm）为一个计算的具体步骤，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和初始输入（可能为空）开始，经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。

算法的特征

以下是高德纳在他的著作《计算机程序设计艺术》里对算法的特征归纳：

• 输入：一个算法必须有零个或以上输入量。
• 输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
• 明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地匹配要求或期望，通常要求实际运行结果是确定的。
• 有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
• 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

算法的基本要素

算法的核心是创建问题抽象的模型和明确求解目标，之后可以根据具体的问题选择不同的模式和方法完成算法的设计。

说起到算法，那么怎样衡量一个算法的好坏呢？答案是通过两方面来考虑，一是从时间上来考虑，也就是所谓的时间复杂度； 还有就是从空间上来考虑，也就是空间复杂度。

时间复杂度

• 算法的时间复杂度是指算法需要消耗的时间资源。

一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做T(n)=O(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 < N，则交换M和N 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 < n)
            swapi(&m, &n);
        r = m % n;
        m = n;
        n = r;
    } while (r);
    return m;
}

好了就讲这么多了，如果有什么问题可以在下面评论或者发私信给我。

参考文章

• 算法