如何在国外社交网站上做原单外贸,vi手册免费模板,北京哪个网站制作公司,网站建设专业简介目录
算法:)
一、定义
二、特征
三、基本要素
常用设计模式
常用实现方法
四、形式化算法
五、复杂度
时间复杂度
空间复杂度
六、非确定性多项式时间#xff08;NP#xff09;
七、实现
八、示例
求最大值算法
求最大公约数算法
九、分类 算法:)
一、定义 …目录
算法:)
一、定义
二、特征
三、基本要素
常用设计模式
常用实现方法
四、形式化算法
五、复杂度
时间复杂度
空间复杂度
六、非确定性多项式时间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 MN}则交换{\displaystyle M}和{\displaystyle N}
②{\displaystyle M}被{\displaystyle N}除得到余数{\displaystyle R}
③判断{\displaystyle R0}正确则{\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计算机术语_百度百科 基本算法 深度优先搜索 广度优先搜索 启发式搜索 遗传算法 枚举 搜索 数据结构的算法 数论与代数算法 计算几何的算法 凸包算法 图论的算法 哈夫曼编码 树的遍历 最短路径算法 最小生成树算法 最小树形图 网络流算法 匹配算法 分团问题 动态规划 其他 数值分析 加密算法 排序算法 检索算法 随机化算法 关于并行算法请参阅并行计算一文。
