00.算法的发展历史
算法的起源可以追溯到我国的古代公元前1世纪的《周髀算经》&＃xff0c;它是算经的十书之一&＃xff0c;算法在我国古代被称为“演算法” 。
在西方公元9世纪波斯数学家al-khwarizmi提出了算法的概念&＃xff0c;算法最初写为algorism&＃xff0c;意思采用阿拉伯数字的运算法则&＃xff0c;到了18世纪&＃xff0c;算法正式命名为algorithm。由于汉字计算的不方便&＃xff0c;所以我国古代算法的发展比较缓慢&＃xff0c;而采用阿拉伯数字的西方国家则发展迅速。
历史上Ada Byron被认为是第一个程序员。她在1842年编写的巴贝奇分析机上的伯努利方程求解算法程序虽然未能执行&＃xff0c;但奠定了计算机算法程序设计的基础。
01.数据结构&＃43;算法&＃61;程序
Pascal之父尼克劳思·沃斯&＃xff08;Nicklaus Wirth&＃xff09;凭借他提出的著名公式“算法&＃43;数据结构&＃61;程序”获得图灵奖。这个公式对计算机科学的影响程度足以类似物理学中爱因斯坦的E&＃61;MC^2 &＃xff0c; 从中可以看到算法和数据结构之间的关系。
算法在教科书中的专业解释&＃xff1a;算法是解决实际问题的一种一种精确描述方法&＃xff0c;算法是对特定问题的求解步骤的一种精确描述方法。目前被广泛认可的算法专业定义是&＃xff0c;算法是模型分析的一组可行的&＃xff0c;确定的和有穷的规则。
通俗的说算法相当于逻辑&＃xff0c;小部分已为人们发掘出来&＃xff08;这里的小部分指的是书本里讲的各种算法&＃xff0c;属于人们对于特定模式抽象出来的核心&＃xff0c;比如排序&＃xff09;&＃xff0c;可以看做一种模式。对应于业务来说&＃xff0c;一种逻辑&＃xff08;可能由其他元子逻辑组合而成&＃xff09;一旦确定下来&＃xff0c;便可看做常量&＃xff0c;固定不变。其次&＃xff0c;算法可以理解为一个完整的解题步骤&＃xff0c;由一些基本的运算和规定的运算顺序构成&＃xff0c;通过这样的解题步骤可以解决特定的一些问题&＃xff0c;从计算机的程序设计角度去看算法由一系列求解问题指令构成&＃xff0c;能够根据规范的输入&＃xff0c;在有限的时间内获得有效的输出结果&＃xff0c;算法代表了用系统的方法来描述解决问题的一种策略机制。
数据结构即数据的组织形式&＃xff0c;可以用来表示特定的数据&＃xff0c;在计算机程序设计中&＃xff0c;操作的对象是各式各样的数据&＃xff0c;这些数据往往由不同的数据结构&＃xff0c;如数组&＃xff0c;结构体&＃xff0c;联合&＃xff0c;指针&＃xff0c;链表等&＃xff0c;因为不同的数据所采用的数据处理方法不同&＃xff0c;计算的复杂程度也不同&＃xff0c;因此算法往往依赖某一种数据结构&＃xff0c;即数据结构是算法实现的基础。
02.算法的基本特征
举一个例子&＃xff0c;假如有你回到了家&＃xff0c;家里没有热水&＃xff0c;也没有女朋友&＃xff0c;整理了一下思路你准备做以下几件事
事件A洗菜 5分钟
事件B烧水 10分钟
事件C泡面 5分钟
事件D扫地 5分钟
以上几件事&＃xff0c;不同的顺序将导致不同的完成时间
如事件按ABCD的顺序做完那么需要25分钟
如事件按BADC的顺序做完那么只需要15分钟
由上面的例子来看&＃xff0c;虽然两种顺序都达到了做完事情的目的&＃xff0c;但是一种方式比第二钟慢了10分钟&＃xff08;为了吃完能多改几个bug我想大多数程序员都会选第二种....&＃xff09;。从这里看出&＃xff0c;算法也是由好坏区别的&＃xff0c;好的算法可以提高工作效率&＃xff0c;获得更好的结果。
一个典型的算法一般可以从中抽取出如下5个特征
1.有穷性
算法的指令或者步骤的执行次数是有限的&＃xff0c;执行的时间也是有限的。
2.确切性
算法的每行一个指令或者步骤都必须由明确的定义和描述。
3.输入
一个算法应该由相应的输入条件&＃xff0c;用来刻画运算对象的初始情况。
4.输出
一个算法应该由明确的输出结果&＃xff0c;没有结果的算法毫无意义。
5.可行性
算法的执行步骤必须是可行的&＃xff0c;且可以在有限的时间内完成&＃xff0c;无法执行的步骤是毫无意义的&＃xff0c;解决不了任何实际问题。
03.算法的分类
1.按照应用来分类
按照算法的应用领域&＃xff0c;即解决的问题&＃xff0c;算法可以分为基本算法&＃xff0c;数据结构相关算法&＃xff0c;几何算法&＃xff0c;图论算法&＃xff0c;规划算法&＃xff0c;数值分析算法&＃xff0c;加密/解密算法&＃xff0c;排序算法&＃xff0c;查找算法&＃xff0c;并行算法&＃xff0c;和数论算法等
2.按照确定性分类
a.确定性算法
确定性算法能在有限的时间内完成计算&＃xff0c;得到的结果是唯一的&＃xff0c;且经常取决于输入值。
b.非确定性算法
非确定性算法能够在有限的时间内完成计算&＃xff0c;但是得到的结果往往是不是唯一的&＃xff0c;存在多值性。
3.按照算法的思路分类
算法可以分为递推算法&＃xff0c;递归算法&＃xff0c;穷举算法&＃xff0c;贪婪算法&＃xff0c;分治算法&＃xff0c;动态规划算法&＃xff0c;和迭代算法等多种算法。
04.算法相关的概念区别
算法是一个抽象的概念&＃xff0c;往往需要依托于具体的实现方式才能体现它的价值&＃xff0c;如在计算机编程中的算法&＃xff0c;数值计算中的算法等&＃xff0c;
1.算法与公式的关系
公式是用于解决某类问题&＃xff0c;有着特定的输入和输出结果&＃xff0c;能够在有限的时间内完成&＃xff0c;并且公式都是可以操作计算的&＃xff0c;但算法并不一定是公式&＃xff0c;公式只是提供了一种算法。
2.算法与程序的关系
传统的笔算中&＃xff0c;通过纸和笔按照一定的步骤完成的计算也是算法的应用&＃xff0c;在速记中&＃xff0c;人们通过特殊的算法来达到快速牢固记忆的目的&＃xff0c;这也是一种算法的应用&＃xff0c;同样&＃xff0c;程序设计语言是算法实现的一种形式&＃xff0c;也是一种工具&＃xff0c;通过熟悉程序设计语言的语法格式&＃xff0c;然后使用程序设计语言编写出实现算法的程序。
3.算法与数据结构的关系
算法是解决问题的一个抽象方法和步骤&＃xff0c;同一个算法在不同的语言中具有不同的实现形式&＃xff0c;其依赖于数据结构的形式和程序设计语言的语法格式&＃xff0c;数据结构往往表示的是处理的对象&＃xff0c;算法是计算和处理的核心方法&＃xff0c;程序设计语言是是算法的设计方式&＃xff0c;其综合构成结果即为程序。可以用公式 数据结构&＃43;算法&＃43;程序设计语言&＃61;程序 来理解。
05.算法的表示
算法是为了解决实际问题的&＃xff0c;一般来说随着问题的难度增加&＃xff0c;算法也会相应的复杂&＃xff0c;为了便于交流和进行算法处理往往需要将算法进行描述&＃xff0c;即算法的表示&＃xff0c;一般来说&＃xff0c;算法可以采用自然语言的表示&＃xff0c;流程图表示&＃xff0c;N-S图表示&＃xff0c;伪代码表示&＃xff0c;
a.自然语言表示
自然语言通俗的讲就是口头描述的语言&＃xff0c;对于一些简单的算法可以采用&＃xff0c;然而很多算法都比较复杂&＃xff0c;很难用自然语言来进行描述&＃xff0c;不利于发展与交流&＃xff0c;所以需要采用其他的方法来进行表示。
b.流程图表示
流程图是一种图形表示算法流程方法&＃xff0c;其由一些图框和流程线组成&＃xff0c;图框表示各种操作的类型&＃xff0c;图框中的说明文字和符合表示该操作的内容&＃xff0c;流程线表示操作执行的顺序。
流程图的优点是简单直观便于理解&＃xff0c;在计算机领域中有着广泛的应用。
计算两个输入数据x和y的最大值的流程图表示
实际使用中&＃xff0c;一般采用如下三种流程结构。
1.顺序结构
顺序结构是最简单的一种结构&＃xff0c;简单地一个接着一个地进行处理&＃xff0c;顺序结构适合于简单的算法。
2.分支结构
分支结构常用用于根据某个条件&＃xff0c;来决定算法的走向&＃xff0c;
3.循环结构
循环结构常用于需要反复执行的算法操作&＃xff0c;按照循环的方式&＃xff0c;可以分为当型循环结构和直到型循环结构。
当型循环结构先对条件进行判断&＃xff0c;然后在执行&＃xff0c;一般采用while语句实现
直到型循环先执行&＃xff0c;然后在对条件进行判断&＃xff0c;一般采用do...while语句实现
c.N-S图表示
N-S图也称为盒图或者CHAPIN图,1973年由美国学者I.Nassi和B.SHneiderman提出&＃xff0c;他们发现采用流程图可以清楚表示算法或者程序的运行过程&＃xff0c;但其中的流程线并不是必须的&＃xff0c;因此创立了N-S图&＃xff0c;在N-S图中&＃xff0c;将整个程序写在一个大框内&＃xff0c;这个大框图由若干个小的基本框图组成&＃xff0c;采用N-S图可以方便的表示流程图的内容。
d.伪代码表示
伪代码&＃xff08;Pseudocode&＃xff09;是另外一种算法的描述方式&＃xff0c;伪代码并非真正的程序代码&＃xff0c;其介于自然语言和编程语言之间&＃xff0c;因此&＃xff0c;伪代码并不能够直接在计算机中运行&＃xff0c;使用伪代码的目的是将算法描述成一种类似编程语言的形式&＃xff0c;这样便可以很容易的理解算法的结构&＃xff0c;再根据编程语言的语法特点&＃xff0c;稍加修改&＃xff0c;即可实现一个真正的算法程序。
伪代码只是像流程图一样用在程序设计的初期&＃xff0c;帮助写出程序流程。简单的程序一般都不用写流程、写思路&＃xff0c;但是复杂的代码&＃xff0c;最好还是把流程写下来&＃xff0c;总体上去考虑整个功能如何实现。写完以后不仅可以用来作为以后测试,维护的基础&＃xff0c;还可用来与他人交流。但是&＃xff0c;如果把全部的东西写下来必定可能会让费很多时间&＃xff0c;那么这个时候可以采用伪代码方式。比如&＃xff1a;
IF 九点以前 THEN
do 私人事务&＃xff1b;
ELSE 9点到18点 THEN
工作&＃xff1b;
ELSE
下班;
END IF
这样不但可以达到文档的效果,同时可以节约时间. 更重要的是,使结构比较清晰,表达方式更加直观。使用伪代码是&＃xff0c;描述应该结构清晰&＃xff0c;代码简单&＃xff0c;可读性好&＃xff0c;这样才能够有利于算法表示。
06.算法的性能评价
算法其实就是解决为的一种方法&＃xff0c;一个问题的解决往往可能有很多种方法&＃xff0c;但每种方法所用时间个得到的效果往往是不一样的。好的算法执行效率高&＃xff0c;所耗费时间短&＃xff0c;差的则相反。算法的一个重要任务就是找到合适的效率最高的解决问题的办法&＃xff0c;即最好的算法&＃xff0c;理论上来讲这就需要对算法有一个合理客观的评价&＃xff0c;一个算法的优劣往往是通过算法的复杂度来测量的&＃xff0c;算法复杂度包括时间复杂度和空间复杂度。
1.时间复杂度
时间复杂度即算法执行所有消耗的时间&＃xff0c;时间越短&＃xff0c;算法越好
算法代码执行的时间往往和算法的执行时间复杂度还于问题的规模&＃xff0c;算法代码中语句执行的数量有关&＃xff0c;由于每一条代码的执行都需要时间&＃xff0c;语句执行的越多&＃xff0c;整个程序执行的时间就越长&＃xff0c;因此&＃xff0c;简短精悍的算法程序往往执行速度快&＃xff0c;
2.空间复杂度
空间复杂度指的是算法程序在计算机中执行所消耗的存储空间。
a.程序保存所需要的存储空间&＃xff0c;即程序的大小
b.程序在执行过程中所需要消耗的存储空间资源&＃xff0c;如程序在执行过程中的中间变量。
京公网安备 11010802041100号