❀My学习小记录之算法❀

目录

算法:)

一、定义

二、特征

三、基本要素

常用设计模式

常用实现方法

四、形式化算法

五、复杂度

时间复杂度

空间复杂度

六、非确定性多项式时间（NP）

七、实现

八、示例

求最大值算法

求最大公约数算法

九、分类

---

算法:)

一、定义

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

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

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

二、特征

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

输入：一个算法必须有零个或以上输入量。

输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。

明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地符合要求或期望，通常要求实际运行结果是确定的。

有限性：依据图灵的定义，一个算法是能够被任何图灵完全系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。

有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

三、基本要素

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

常用设计模式

完全遍历法和不完全遍历法：在问题的解是有限离散解空间，且可以验证正确性和最优性时，最简单的算法就是把解空间的所有元素完全遍历一遍，逐个检测元素是否是我们要的解。这是最直接的算法，实现往往最简单。但是当解空间特别庞大时，这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。

分治法：把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。

动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。

贪心算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。

线性规划法：见条目。

简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。

常用实现方法

递归方法与迭代方法

顺序计算、并行计算和分布式计算：顺序计算就是把形式化算法用编程语言进行单线程序列化后执行。

确定性算法和非确定性算法

精确求解和近似求解

四、形式化算法

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

五、复杂度

时间复杂度

算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n的函数f(n)，算法的时间复杂度也因此记做

算法执行时间的增长率与f(n)的增长率正相关，称作渐近时间复杂度，简称时间复杂度。

常见的时间复杂度有：常数阶O(1)，对数阶，线性阶 O(n)，线性对数阶，平方阶，立方阶，...，k次方阶,指数阶。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低 。

空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

六、非确定性多项式时间（NP）

主条目：NP (复杂度)

七、实现

算法不单单可以用计算机程序来实现，也可以在人工神经网络、电路或者机械设备上实现。

八、示例

求最大值算法

这是算法的一个简单的例子。

我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小，可以将下面的算法形象地称为“捡豆子”：

①首先将第一颗豆子放入口袋中。

②从第二颗豆子开始检查，如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。反之则继续下一颗豆子。直到最后一颗豆子。

③最后口袋中的豆子就是所有的豆子中最大的一颗。

以上算法在中国大陆的教科书中通常被叫做“打擂法”或者“循环打擂”：在一个for循环中，每轮循环都有新的挑战者。若挑战者胜的话，挑战者做新擂主，否则擂主卫冕。for循环结束后输出最后的擂主。

下面是一个形式算法，用ANSI C代码表示

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 M<N}，则交换{\displaystyle M}和{\displaystyle N}

②{\displaystyle M}被{\displaystyle N}除，得到余数{\displaystyle R}

③判断{\displaystyle R=0}，正确则{\displaystyle N}即为“最大公约数”，否则下一步

④将{\displaystyle N}赋值给{\displaystyle M}，将{\displaystyle R}赋值给{\displaystyle N}，重做第一步。

用ANSI C代码表示

//交换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, &n);        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;
}

九、分类

本文学习来源：algorithm（计算机术语）_百度百科

• 基本算法

  • 深度优先搜索

  • 广度优先搜索

  • 启发式搜索

  • 遗传算法

  • 枚举

  • 搜索

• 数据结构的算法

• 数论与代数算法

• 计算几何的算法

  • 凸包算法

• 图论的算法

  • 哈夫曼编码

  • 树的遍历

  • 最短路径算法

  • 最小生成树算法

  • 最小树形图

  • 网络流算法

  • 匹配算法

  • 分团问题

• 动态规划

• 其他

  • 数值分析

  • 加密算法

  • 排序算法

  • 检索算法

  • 随机化算法

  • 关于并行算法，请参阅并行计算一文。