网站后台放在哪里,苏州做网站0512jinyan,外贸网站打开速度,教你做吃的网站1.0 前言
算法#xff08;Algorithm#xff09;是指解题方案的准确而完整的描述#xff0c;是一系列解决问题的清晰指令#xff0c;算法代表着用系统的方法描述解决问题的策略机制。也就是说#xff0c;能够对一定规范的输入#xff0c;在有限时间内获得所要求的输出。 …1.0 前言
算法Algorithm是指解题方案的准确而完整的描述是一系列解决问题的清晰指令算法代表着用系统的方法描述解决问题的策略机制。也就是说能够对一定规范的输入在有限时间内获得所要求的输出。
简单地说算法其实是解决问题的方法他不是属于计算机方面的一个专属名词。不正式的说算法是任何定义明确的计算过程比如买菜大妈的买菜策略骗子的坑人步骤再比如高考中数学的立体几何有的人写二十行有的人写四十行他们都写上了属于自己的算法但是效率不同。
复杂一点的再比如一个环卫工人要清扫五个地点 她也有不止一种执行完这个任务的方法 那到底哪种方法走的路比较少这就是我们之后要学习的最短路算法。 下面举一个例子来了解算法
我们从小都见过的小学奥数题有一口井七米深一只青蛙从井底爬上来白天爬了三米晚上掉下两米这样它要爬几天才能上来
我们最笨的解题步骤
让青蛙爬三米判断是否爬上去了让青蛙掉下两米重复上述过程并记录天数
而不是计算得出一天爬一米得出七天爬上来
或者另一种算法
最后一天直接爬上去7-34米其余天一天一米路程/速度4天415天
由此可见我们首先要保证算法的正确性其次要保证算法的效率我们比较一下上述算法
计算得出一天爬一米得出七天爬上来这种算法是错误的模拟法让青蛙模拟整个爬井的过程我们看看有几次运算
03337
3-21
次数011 13447
4-22
次数112 03357
5-23
次数213 03367
6-24
次数314 43377爬出来了
次数415
一共进行了19次运算
公式法7-343-214/14
进行了3次运算 从这个对比中应该能感受到算法不同效率差距是很大的然而感受其实的还不够。
试想
假如这口井是100米1000米10000米随着深度的增加模拟法的计算次数也再增加和深度成正比。
而再看公式法其实和深度并没有什么关系不管深度是多少公式法永远只用计算3次即可。
这种计算次数和条件的大小数量等因素没有关系的算法视为非常优秀的一种算法。 那我们计算机的算法到底是什么我们提到算法不是计算机领域才拥有的概念它可以用任何方式来描述我们之前接触到的基本都是用文字来表达比如我在上文中列出的解题步骤。而我们要干的事或者说计算机的算法要干的事就是用代码来描述计算机上的处理过程。我们用一行行的语句来描述一个个解决问题的方法这就是编程。 计算机所有算法都是通过基本语句一点点描述出来的比如上文的模拟算法
让青蛙爬三米判断是否爬上去了让青蛙掉下两米重复上述过程并记录天数
其中涉及到编程的很多基本语句加减法、条件判断语句、循环语句等编程语言也有很多但是只是一个工具而已就和汉语英语一样并且单词数量比这两种语言少很多。所以只要脑海中的思路足够清晰我们用一种编程语言把它描述出来即可而不是我们之前去用汉语描述。 事实上计算机的算法解决的问题可能是更加实际的问题关系着我们每个人的生活比如地图app如百度地图高德地图是如何帮你规划的路线的再比如双十一如此疯狂的购物各大购物网站是如何保证不会崩溃的再比如到现在还没解决的问题微博到现在为止志玲姐姐结个婚服务器都会崩。
如何衡量一个算法到底优不优秀我们下篇来讲。 1.1何为算法
算法Algorithm是指解题方案的准确而完整的描述是一系列解决问题的清晰指令算法代表着用系统的方法描述解决问题的策略机制。也就是说能够对一定规范的输入在有限时间内获得所要求的输出。
如果一个算法有缺陷或不适合于某个问题执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
下面为算法的五个特性 有穷性Finiteness
算法的有穷性是指算法必须能在执行有限个步骤之后终止 确切性(Definiteness)
算法的每一步骤必须有确切的定义 输入项(Input)
一个算法有0个或多个输入以刻画运算对象的初始情况所谓0个输入是指算法本身定出了初始条件 输出项(Output)
一个算法有一个或多个输出以反映对输入数据加工后的结果。没有输出的算法是毫无意义的 可行性(Effectiveness)
算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步即每个计算步都可以在有限时间内完成也称之为有效性。 1.2衡量算法的指标
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
用几句话简单说明一下时间复杂度。
时间复杂度并不是表示一个程序解决问题需要花多少时间而是当问题规模扩大后程序需要的时间长度增长得有多快。也就是说对于高速处理数据的计算机来说处理某一个特定数据的效率不能衡量一个程序的好坏而应该看当这个数据的规模变大到数百倍后程序运行时间是否还是一样或者也跟着慢了数百倍或者变慢了数万倍。
1不管数据有多大程序处理花的时间始终是那么多的我们就说这个程序很好具有O(1)的时间复杂度也称常数级复杂度
2数据规模变得有多大花的时间也跟着变得有多长这个程序的时间复杂度就是O(n)比如找n个数中的最大值
3而像冒泡排序、插入排序等数据扩大2倍时间变慢4倍的属于O(n^2)的复杂度。
4还有一些穷举类的算法所需时间长度成几何阶数上涨这就是O(a^n)的指数级复杂度甚至O(n!)的阶乘级复杂度。
注意不会存在O(2*n^2)的复杂度因为前面的那个“2”是系数根本不会影响到整个程序的时间增长。同样地O (n^3n^2)的复杂度也就是O(n^3)的复杂度。
因此我们会说一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低尽管在n很小的时候前者优于后者但后者时间随数据规模增长得慢最终O(n^3)的复杂度将远远超过O(n^2)。我们也说O(n^100)的复杂度小于O(1.01^n)的复杂度。 而空间复杂度是相似的只是他的单位不是时间而是空间可以认为是内存。 2.1计算机
说完算法我们来谈谈计算机吧。
计算机的优势非常明显速度、记忆、精确但是它也不是万能的。
就算计算机速度快也不可以给他无限大的工作量就算计算速度再快的计算机在O(N^N)等复杂度的算法面前也是无能为力具体使用那种算法是人说了算计算机无条件执行这就对编程的人提出了要求。 计算机的容量是非常大的但是也不能存无限多的东西同样的问题解决方法不同花费的空间差异也是巨大的。 计算机是精确的但是解决问题的方法和人类不一样比如计算机很难回答某件物品“美不美”“值不值”再比如很多算法对人类是很直观的可以用语言描述但是转化成机器语言会花很多时间。 总而言之请善待你的计算机啦。
