欢迎来到奇葩栖息地!欢迎加入Discord服务器:XfrfHCzfbW本站借助问谛居的服务器搭建,感谢倾情援助。本站处于基础建设阶段,欢迎参与建设工作。不会编辑?请至这里学习Wikitext语法。

算法基础

来自奇葩栖息地
此页面使用了SimpleMathJax扩展渲染的TEX公式。

这些公式被包含在<math><chem>标签中,请稍等片刻等待前端渲染。

算法(Algorithm)是程序的根基。这篇文章简要介绍了啥是算法,以及作为一个coder必须知道的一些事。

算法

众所周知,计算机是无生命的。所以要是想让它做人类想让它做的事情的话,人类就不得不付出劳动。(悲)

至于AI人工智障啊,机器学习啊,他们的根基都离不开算法

那么算法是啥?

就好比如果你要做菜,那你就应该知道怎么做菜(废话)。至于这个“怎么做菜”,这就是算法。再好比你打游戏,你怎么去打这个游戏,比如按照攻略打,又比如卡bug去打,“怎么打游戏”也是算法。说白了,算法就是解决一个“How”的问题。再升级到怎么统筹规划,怎么解数学题,都是算法。

所以算法是很重要的。但是算法这个东西你又不能让计算机去学,所以只能你自己学。(悲)

所以我们就开始学吧,在学之前,我们要先了解一点东西。

复杂度

下面两种复杂度决定了一个代码的综合效率。(但作为一个coder更关心的还是一个算法的代码复杂度,这在有时间限制的算法竞赛中还是很重要的。)

时间复杂度

回到刚才打游戏的例子。有的游戏里面会给玩家搞一个排行榜,比如说刷副本,这个人刷了多长时间,那个人又刷了多长时间,从快到慢依次排下来,就是一张榜。当然了,打游戏的这个时长是可以熟能生巧来练的,但是算法的时间效率是你想出来之后就固定了的。

算法的时间效率,OIer一般称作时间复杂度。时间复杂度又分好几种类型,我们一般使用渐进上界复杂度,记为[math]\displaystyle{ O }[/math](说白了就是算法用时的最坏情况,有些时候实际不需要运行这么长时间)。

那么这个时间复杂度怎么算呢?

最简单,也是初学者最常用的一种算法就是看这个算法循环了几层数据规模。设数据规模为[math]\displaystyle{ N }[/math],假如一个算法只是对几个数进行了简单的运算,它的时间效率跟[math]\displaystyle{ N }[/math]的大小没有半毛钱关系,那么称这种算法的时间复杂度是[math]\displaystyle{ O(1) }[/math]的,是所有算法中效率最高的一种。又假如一个算法它从[math]\displaystyle{ 1-N }[/math]遍历了一遍,时间效率跟[math]\displaystyle{ N }[/math]的大小成正比,那么称这种算法的时间复杂度是[math]\displaystyle{ O(N) }[/math]的,又称为线性复杂度(因函数[math]\displaystyle{ y=x }[/math]的图像是一条直线而得名)。再假如一个算法从[math]\displaystyle{ 1-N }[/math]遍历了一遍,每次遍历的时候又从[math]\displaystyle{ 1-N }[/math]遍历了一遍,时间效率跟[math]\displaystyle{ N^2 }[/math]的大小成正比,那么称这种算法的时间复杂度是[math]\displaystyle{ O(N^2) }[/math]的,以此类推。

顺便一说,时间效率有时候也是可以超过渐进上界复杂度的,重点在于复杂度中的常数。我们刚才列出的时间复杂度都是单纯的字母量,但程序实际运行时往往这个字母量前面会有常数系数,甚至会带有次数更低的字母(比如说[math]\displaystyle{ T(N^2+N) }[/math])。所以就专门有一个符号[math]\displaystyle{ T }[/math],指程序实际上的时间复杂度,用[math]\displaystyle{ T }[/math]的时候可以带有常数和低次的字母。但在大[math]\displaystyle{ O }[/math]记号中这些通常都被省略不写,因为数据规模很大,常数的数量级很小,往往可以忽略不计。

时间复杂度也有很多玄学的算法。比较容易理解的一种说法就是,算法的时间效率跟数据规模的什么运算成正比,时间复杂度就用数据规模的什么运算表示,比如常见的还有[math]\displaystyle{ O(\sqrt{N}) }[/math][math]\displaystyle{ O(\log N) }[/math](因为可以用换底公式转化成常数,所以底数通常也省略不写),[math]\displaystyle{ O(2^N) }[/math][math]\displaystyle{ O(N!) }[/math]等。

空间复杂度

空间复杂度,就是一个算法的空间效率。这取决于它占用你电脑内存的多少空间,通常也用[math]\displaystyle{ O }[/math]来表示。空间复杂度一般不是很重要,但是只要它重要了就会特别重要,能掌握算法命运的那种。

语言和代码

语言很重要,但hsy不怎么懂

市面上比较流行的语言大概就是C++、Java、Pascal以及Python等等。语言也分不同的类型,有面向对象的,有函数式的,有指令式的,相同点就是都是高级语言。高级语言就得编译成计算机能识别的机器语言,所以在编程之前得先学语言并且下载一个编译器。

以后讲算法的文章hsy都将使用C++作为示范,因为不会其他的

至于代码,就是仁者见仁智者见智的东西。有的算法写成代码会有很多种不同的写法,甚至复杂度也会有微小的区别。码风(代码风格)就更是一人一个样了。主要还是效率至上,其他方面自己喜欢即可。