• 藏在我们生活中的那些算法
  • 发布于 2个月前
  • 242 热度
    0 评论
算法的定义
算法(algorithm)在数学(算学)和计算机科学之中,为任何良定义的具体计算步骤的一个序列,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。

算法中的指令描述的是一个计算,当其运行时能从一个初始状态和初始输入(可能为空)开始,经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法,包含了一些随机输入。

上面是来自维基百科对于算法的定义,相信很多人看完以后应该是这样的表情。

本科 CS 算法的学习

一位程序员想要进阶到高级阶段,成为人们所说的编程大牛。那算法这门艺术是必须掌握。但国内大部分本科对于算法的教育可以用失败来形容,更不用说那些培训出身的程序员。普通 CS 本科的学生,算法是他们的必修课。但 95% 的科班生对于算法的理解仅限于知道有个时间复杂度、空间复杂度。稍微厉害点的可能还知道递归、二叉树、最小生成树、有向图、红黑二叉查找树。但要叫他们写一个最简单的排序算法,大部分人都写不出来。

我大学就读于某个普通二本,学的就是计算机专业。算法这门课是我大三上学期学习的课程。那时候教我们的老师,算法功力非常深厚,对于各种算法了如指掌,像插入排序、冒泡排序、希尔排序、快速排序、深度优先搜索、广度优先搜索等等这些算法,老师闭着眼睛都可以写的出来。但即使这样博学的老师,仍然不能把算法教好。我们班的学生经过一学期的算法学习,大部分人连最基础的排序都不会写。一学期的算法课,大家倒是了解很多算法的概念。

而导致这样的情况,本质是因为大学对于算法的教学是有很大的问题。算法这门课本身就是非常深奥的一门学科,很多人在没上大学之前根本就没接触过。大家都是算法小白。然后大学对小白的教育就是教一大堆难懂的概念。先来一波概念教学,教你什么是空间复杂度,什么是时间复杂度,什么是递归,什么是二叉树,什么是有向图、什么是 Dijkstra 算法、什么是递归懵逼。

各种让人头大的概念,先安排一波。这就像让一位小学生先去学习高中数学的内容,国内又能有几个小学生能学懂?有多少人在最开始学习算法就抱着一本《算法导论》苦啃。学习没几页就被里面各种难懂的概念所难倒,然后就放弃算法的学习。

计算机这门学科本身就是注重理论和实践相互结合。大部分的理论就是为了解决实际生活中的问题。而国内计算机的教育都只注重理论,却完全忽略实践。这样教出来的学生千篇一律,只懂一大堆理论知识,却连一个最简单的管理系统都做不出来。最可笑的是我本系的计算机同学,在大四临近毕业的时候,还要花上万的费用,去培训机构学习。这就是你们眼中的科班生。

生活中的算法思想
最开始算法学习的确非常的枯燥,记得自己最初为了记住「插入排序」这 9 行代码,我花上了两天的时间。就是下面这几行代码。

各种不能理解其中的门道。然而当你理解了其中的思想,其实算法是非常有趣的一门学科。利用算法的思想去解决生活中的问题,会产生许多非常有趣的事情。

比如在知乎上有这样的一个问题「你在生活中用过最高级的算法知识是什么?」

其中的一些问答:
1 二分找肉法

吃串串火锅,就是火锅里面煮肉串的。串非常长,一端串着肉。由于很多人吃,串放在锅里很多,所以大多数肉串都掉进汤里了。

我手里有近  30 个串,但是一看末端,只有一片肉。末端我是不愿意碰的,因为上面都是油。所以我只能从另一端来挑出来那片有肉的串。

那么在最坏情况下,我需要 O(n),也就是 30 次挑选才能选出来那根有肉的串。

于是我发明了二分找肉法,首先把手里的串分成等量的两份,看肉在哪一份。然后对有肉的那一份进行同样操作,直到 n = 1 为止。

复杂度从 O(n)降为 O(logn),只需要 5 次挑选。

在我发明算法并且找到肉的这段时间里,朋友已经把锅里的肉都吃完了。

2 打牌时的插入法

生活中打牌时用的就是插入排序。

3 按学号快速排作业法

老师让我把全班 60 本作业本按封面上的学号排好。于是我灵活运用了快速排序的知识,从本堆中随便抽出一本,把学号比它小的本子放在左边,学号比它大的本子放在右边,再从左边这一堆挑出一本……

如此一来我的排本子的时间复杂度就从普通人用的插入排序的  O(n²)  变成了 O(n log n)。周围的同学投来好奇的目光,我洋洋自得,心想学过算法的我就是不一样。快速排序效率果然很高,不一会儿,我的桌子就放不下了_(:з」∠)_。

兴趣是所有学习最好的老师

通过上面生活中的算法实例,虽然有些算法还有缺陷,但是不是觉得算法好像挺有趣的?算法还有这种操作?当然如果你没有学习过算法,对于二分查找法、插入排序法可能你不太明白。但通过这样生动有趣的生活实例,一下子就提高你对算法的好感度。紧接着你为了弄明白其中的算法思想,你会主动去查找相关的资料。

这样的兴趣驱动学习,是我一直想对大家强调的一点。不要在刚开始接触编程语言的时候,就陷入无止境的概念学习。有些概念真的非常难懂,但不要紧,你可以暂时的跳过。等你对编程学习的深入,在回头看看以前觉得很难的地方,就会有种海阔天空的感觉。这就好比你现在回头看看初中的数学一样,觉得以前的数学好简单。不要因为一些暂时不能理解的内容,就让你失去学习的信心,放弃了编程的学习。

在编程中找到乐趣是一个程序员的基本素养。

用户评论