2021年信息学部物联网工程学院学生科协算法科普

一、什么是算法

在数学领域里&＃xff0c;算法是用于解决某一类问题的公式和思想。 计算机领域的算法本质上是用于解决特定问题的指令序列。它和数学上的算法有许多共通之处。比如&＃xff0c;他们都是为了解决某一问题&＃xff0c;或者是简化某一问题的解决步骤而生的&＃xff1b;他们都体现了一些计算的思路等等。

二、算法重要吗

真正学懂计算机的人&＃xff08;不只是“编程匠”&＃xff09;都对数学有相当的造诣&＃xff0c;既能用科学家的严谨思维来求证&＃xff0c;也能用工程师的务实手段来解决问题——而这种思维和手段的最佳演绎就是“算法”。

算法在我们日常生活中也有着很广泛的应用。比如我们的导航&＃xff0c;就是靠着一些关系和图论相关的算法&＃xff0c;帮我们找到最佳路线。双十一&＃xff0c;就更不用说了&＃xff0c;面对一分钟上百亿的交易流水&＃xff0c;保证交易不延迟&＃xff0c;不出错&＃xff0c;这也是算法在背后发挥着作用。

三、算法有好坏吗

一般来说&＃xff0c;我们评价一个算法的好坏一般可以从四个角度去分析&＃xff0c;时间复杂度、空间复杂度、正确性和健壮性。
在判断一个算法的好坏时&＃xff0c;我们往往最关心的、也是最直观的就是时间复杂度。
时间复杂度是定性描述算法运行时间的一个指标&＃xff0c;通常用大O表示法表示。通常&＃xff0c;我们总是希望时间复杂度越低越好。

四、常用算法介绍

1.查找算法

概述

查找是在大量的信息中寻找一个特定的信息元素&＃xff0c;在计算机应用中&＃xff0c;查找是常用的基本运算&＃xff0c;例如在学生表里找到指定学生姓名的学号。

顺序查找

顺序查找即从线性表的第一个元素开始&＃xff0c;逐一向后查找&＃xff0c;知道找到想找的元素或查找失败。

二分查找

二分查找是一种在每次比较之后将查找空间一分为二的算法。

举例&＃xff1a;在下列升序列表中查找48。

第一次查找

第二次查找

第三次查找

2.排序算法

概述

在生活中&＃xff0c;我们离不开排序。例如上体育课时&＃xff0c;同学们会按照身高 顺序进行排队&＃xff1b;又如每一场考试后&＃xff0c;老师会按照考试成绩排名次。
在编程的世界中&＃xff0c;应用到排序的场景也比比皆是。例如当开发一个 学生管理系统时&＃xff0c;需要按照学号从小到大进行排序&＃xff1b;当开发一个电商平台时&＃xff0c;需要把同类商品按价格从低到高进行排序等等。

冒泡排序

选择排序

快速排序

基本思想
选择一个基准数&＃xff0c;通过一趟排序将要排序的数据分割成独立的两部分&＃xff0c;其中一部分的所有数据都比另外一部分的所有数据都要小。然后再按此方法对这两部分数据分别进行快速排序&＃xff0c;整个排序过程可以递归进行&＃xff0c;以达到全部数据变成有序。

3.图的搜索算法

概述

搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况&＃xff0c;从而求出问题的解的一种方法。

深度优先搜索

• 核心思想&＃xff1a;一条道走到黑、不碰南墙不回头。
• 做法&＃xff1a;从某个顶点出发&＃xff0c; 首先访问这个顶点&＃xff0c; 然后找出刚访问这个节点的第一个未被访问的子节点&＃xff0c;然后再以此子节点为顶点&＃xff0c; 继续找它的下一个顶点进行访问。重复此步骤&＃xff0c;直至所有节点都被访问完为止。

广度优先搜索

• 核心思想&＃xff1a;一石激起千层浪
• 做法&＃xff1a;将树按照层级层层遍历&＃xff0c;直到某一层全部遍历完毕再遍历下一层级&＃xff0c;直到所有节点全部遍历完成。

4.贪心算法

核心思想

不从整体最优上加以考虑&＃xff0c;仅考虑局部最优解。

举例

假如你是学校教务老师&＃xff0c;你有如下课程表&＃xff0c;你希望将尽可能多的课程安排在某间教室上。

思路&＃xff1a;
从日常生活角度看&＃xff0c;我们一般会考虑最早结束的课放在最前面上。我们模仿这样的思想&＃xff0c;那么这些课程里最早结束的就是美术。我们把他放在第一节。所以从9点到10点这个时间段内就被占用了&＃xff0c;而10点到12点就是完整的空闲时间。然后我们从10点开始找最早结束的&＃xff0c;也就是数学。现在9点到11点都已经安排好了。最后我们再把音乐安排上去。这样&＃xff0c;仅从局部最优考虑&＃xff0c;也得到了全局最优解。

总结

总是作出当前看来最好的选择。也就是说贪心算法并不从整体最优考虑&＃xff0c;他所做出的选择只是在某种意义上的局部最优选择。但对许多问题它能产生整体最优解。在一些情况下&＃xff0c;即使贪心算法不能得到整体最优解&＃xff0c;其最终结果却是最优解的很好近似。

5.动态规划

核心思想

动态规划与分治思想类似&＃xff0c;通过解决子问题后组合子问题的解来来求解原问题。

举例

假设你是个贪婪的小偷&＃xff0c;背着可装4磅重东西的背包&＃xff0c;在商场伺机盗窃各种可装入背包的商品。 你力图往背包中装入价值最高的商品&＃xff0c;你会怎么呢&＃xff1f;

• 方法一&＃xff1a;穷举
  将8种可能的情况一一列出&＃xff0c;找出可行的最优解。
  
  存在的问题&＃xff1a;当数据量增大时&＃xff0c;该方法需要枚举的可能性将按指数规律增长&＃xff0c;即该算法的时间复杂度为O(2n)O(2^n)O(2n)。在解决实际问题时显然不可行。
• 方法二&＃xff1a;动态规划
  ①先把4磅的大背包拆分成1磅、2磅、3磅、4磅这四种规格。
  也就是说&＃xff0c;一个4磅的大背包可以通过小背包组合而成。
  ②先考虑只偷吉他
  
  ③再考虑偷吉他和笔记本
  
  
  
  
  ④最后考虑偷吉他、笔记本和音箱
  
  
  此时&＃xff0c;原问题的结果被我们通过对子问题的结果进行组合解决了&＃xff0c;答案就是3500美元。