算法基础

众所周知，计算机是无生命的。

所以要是想让它做人类想让它做的事情的话，人类就不得不付出劳动。（悲）

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

那么算法是啥？

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

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

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

复杂度

时间复杂度

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

算法的时间效率，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++ 作为示范，因为不会其他的。

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

大概就讲这么多。