算法与数据结构

算法与数据结构算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。通常,每个问题的解决都经过以下两个步骤: 1

大家好,欢迎来到IT知识分享网。

算法与数据结构

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。

有不少书叫“数据结构与算法分析”这样的名字,那么到底是只讲数据结构呢,还是和算法一起讲?他们之间有什么关系呢?干嘛要放在一起?

我们可以从分析问题的角度去理清数据结构和算法之间的关系。通常,每个问题的解决都经过以下两个步骤:

1.分析问题,从问题中提取出有价值的数据,将其存储;

2.对存储的数据进行处理,最终得出问题的答案;

数据结构负责解决第一个问题,即数据的存储问题。通过前面的学习我们知道,针对数据不同的逻辑结构和物理结构,可以选出最优的数据存储结构来存储数据。

而剩下的第二个问题,属于算法的职责范围。算法,从表面意思来理解,即解决问题的方法。我们知道,评价一个算法的好坏,取决于在解决相同问题的前提下,哪种算法的效率最高,而这里的效率指的就是处理数据、分析数据的能力。

两种算法的比较

大家已经学过至少一门计算机语言,不管学的是哪一种,学得好不好,好歹可以写一些小程序了。现在要求写一个求 1+2+3+……+100结果的程序,应该怎么写呢?

大多数人会马上写出下面的代码:

算法与数据结构

这是最简单的计算机程序之一,它就是一种算法,我不去解释这段代码的含义了。问题在于,你的第一直觉是这样写的,但这样是不是真的很好?是不是最高效?

此时,不得不把伟大数学家高斯的童年故事拿来说一遍,也许你们早已听过,但不妨在感受一下,天才是如何展示天分和才华的。

18世纪生于德国小村庄的高斯,上小学的一天,课堂很乱,老师很生气,后果很严重。于是老师在放学时,就要求每个学生都计算 1+2+3+……100 的结果,谁先算出来谁先回家。

天才当然不会被这样的问题难倒,高斯很快就得出了答案,是 5050,老师非常惊讶,因为他自己想必也是通过 1+2,3+3,6+4,…..,这样算出来的,也算了很久很久。说不定为了怕错,还算了两三遍。可眼前这个少年,为何可以这么快得出结果?

高斯解释道:

算法与数据结构

用程序实现如下:

算法与数据结构

很显然,用这种方法就算计算一千,一万,甚至一亿的加法运算,也就是一瞬间的。人脑比电脑算得快,似乎成为了现实。

算法的特性

  1. 输入输出:算法具有零个或多个输入,至少有一个或多个输出
  2. 有穷性:指的是算法在执行优先的步骤之后,自动结束而不会出现无限循环,并且每个步骤在可以接收的时间内完成。现实中经常会写出死循环的代码,这就是不满足有穷性。当然有穷并不是纯数学意义的,而是在实际应用中合理的。可以接受的边界。假如写一个算法,需要算上二十年,一定会结束,在数学上是有穷了,可以媳妇都熬成婆了,算法的意义也不大了。
  3. 确定性:算法的每一步骤都具有明确的含义,不会出现二义性
  4. 可行性:算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限次数完成

算法设计的要求

  1. 正确性:算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能得到问题的正确答案
  2. 可读性:算法设计的另一母的是为了便于阅读、理解和交流
  3. 健壮性:当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果

设计算法应尽量满足时间效率高和存储量低的需求

在生活中,人们都希望花最少的钱,用最短的时间,办最大的事情,算法也是一样的思想,最好用最少的存储空间,花最少的时间,办成同样的事就是好的算法。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/50398.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信