107874017
本帖最后由 107874017 于 2019-4-27 11:10 编辑

在这里获得更好的阅读体验

  1. # 简单算法入门教程

  3. 由于作者习惯的缘故 本教程代码全部使用C++编写

  5. ## 前言

  7. > 算法是什么？

  9. 对一组规范的输入,合适的算法可以在有限时间内获得所要求的的输出

  11. > 为什么要学算法？

  13. 算法是程序的灵魂,高效的算法是写出高效程序,引领项目的必由之路,光做一个增删改查的程序猿是不够的

  15. ~~还能装13~~

  17. > 有什么比较好的算法教程吗？

  19. 竞赛党：入门程度可以参考刘汝佳的《算法竞赛入门经典》

  21. 进阶后可以参考李煜东的《算法竞赛进阶指南》

  23. 工作党：《数据结构与算法分析（C语言/Java语言描述）》第三版
  24. 《算法导论》第三版（不建议通读）
  25. 《算法》第四版

  27. > 我有什么理由相信你的算法能力？

  29. NOIP2018提高组**一等奖

  31. 现役省选选手

  33. > 我可以在什么地方练习算法？

  35. 假定你的项目并不需要写你想要练习的算法

  37. 你可以在[洛谷](www.luogu.org)或[牛客](nowcoder.com)或者[LeetCode](leetcode-cn.com/)做题

  39. 当然如果你觉得你的水平十分的高 那么你可以在[bzoj](lydsy.com)做往年的NOI省队选拔赛真题

  41. 这些网站基本都支持Java

  43. > 这篇教程会以什么顺序讲算法？

  45. 第一部分会讲几个比较简单的入门算法以及概念

  47. 之后的所有算法均可按自己喜好学习



  51. 同时本教程默认所有读者都有充足的语言基础

  53. 由于篇幅限制 本教程不会非常详细的讲解每个算法

  55. ## 0x00 入门

  57. ### 0x01 时空复杂度

  59. 我们知道算法的效率有快慢之分,但是如果仅仅通过"快","慢"这样的说法描述一个算法,是十分模糊而不可行的。

  61. 于是我们引入了时空复杂度的概念,分为时间复杂度和空间复杂度。

  63. 时间复杂度一般表现为一个函数$T$或函数$O$ ,它反映了算法的运行时间和输入数据规模的关系

  65. 另外需要注意的是 在教程中 绝大多数的时空复杂度都默认输入数据的规模为n

  67. $T$函数可以比较精确的反应一个算法的这种关系 我们举个例子来理解这个函数

  69. 比如说我们定义了一个函数

  71. ```cpp
  72. int func(int n){
  73.     int ans = 0;
  74.     for(int i=1;i<=n;i++)
  75.         ans += i;
  76.     return ans;
  77. }
  78. ```

  80. 可以看出 func的作用是求$\sum_{i=1}^ni$

  82. 对于输入的一个数n 这个算法需要进行的计算次数在n次左右 于是我们认为这个算法的复杂度为$T(n)$



  86. 但是你发现这样写太傻了 因为高斯在很久以前就说过

  88. $\sum_{i=1}^ni=\frac{n*(n+1)}2$

  90. 于是你把这个函数写成了

  92. ```cpp
  93. int func(int n){
  94.     return n*(n+1)/2
  95. }
  96. ```

  98. 现在,由于计算一个乘法的时间是固定的,与输入规模（这里指n的大小）无关,我们说这个算法的复杂度是$T(1)$。



  102. 但是我们发现用$T$来表示一个算法的复杂度比较麻烦 因为如果遇到这种代码：

  104. ```cpp
  105. int func(int n){
  106.     for(int i=1;i<=n;i++){
  107.         for(int j=1;j<=n;j++){
  108.             printf("%d %d\n",i,j);
  109.             for(int k=1;k<=n;k++)
  110.                 printf("%k\n",k);
  111.         }
  112.     }
  113. }
  114. ```

  116. 我们在分析复杂度的时候就应该是$T(n?+n?)$ 因为第四行被执行了$n?$次而第六行被执行了$n?$次（三重循环,n?）

  118. 所以我们需要一个比较简单的函数来描述复杂度 于是我们选择了大O记号

  120. $O$一般指算法的**渐进时间复杂度**

  122. 它的计算方式比较玄学

  124. 首先我们需要选择一个函数$f(n)$ 使得$\lim_\limits{n\rightarrow\infty}\frac {T(n)}{f(n)}=k(k\not=0)$

  126. 那么我们就可以让$O(f(n))$来表示这个算法的时间复杂度

  128. 如果你看不懂上面的说法 你可以简单的理解为算法的计算次数在$f(n)$左右

  130. 如果你还是不懂 你可以认为$f(n)$就是只保留$T(n)$的最高次项,例如$T(n?+n?) -> O(n?)$,
  131. 因为随着n逼近无穷大,n?相对于n?是无穷小,不起决定作用。

  133. 一般来说 $f(n)$会取到$logn(多见于二分算法),n(多见于递归),nlogn,nlog?n,n?(多见于多重循环),n!$之类的简单而好看的函数

  135. 我们再拿上面那段代码举例 此时的渐进时间复杂度就应该是$O(n?)$

  137. 按照现在的比较大众的CPU效率 常数比较优秀的算法可以在一秒内执行大约$10^8$次运算

  139. 换句话来说 当你将$n$带入到大O记号内计算后得出的结果如果在$10^8$以内 那么你的算法就**差不多**可以在一秒内得出结果



  143. 空间复杂度的计算方式与时间复杂度相似 不再赘述



  147. ### 0x02 模拟&暴力

  149. 当我们需要解决一个问题时 我们可以按照这个问题的思路去直接实现算法

  151. 再以求$\sum_{i=1}^ni$为例

  153. 我们可以直接从1枚举到n 再将它累加进答案

  155. 当我们这么做的时候 这个做法就称为模拟 有时也可以叫做暴力

  157. 一般情况下模拟的时间复杂度会比较高

  159. ~~当然我相信有能力写项目的人的模拟水平一般都不会差~~



  163. 举例来说

  165. [[jsoi2007]麻将](www.luogu.org/problemnew/show/P4050)

  167. 题目大意：

  169. 给定$3m+1$张麻将中的牌 每张牌只有序数没有花色

  171. 同时给出序数的范围$n$

  173. 问所有听的牌

  175. 本题不考虑七对子

  177. $9\leq n\leq 400,4\le m\le 1000$



  181. 首先我们要了解麻将和牌的规则 如果不了解 可以百度一下

  183. 我们会发现在和的牌中只有要求的一个对子是比较特殊的

  185. 那么我们可以

  187. - 用一个长度为n的数组来表示手上有的牌（数组下标为i时的值表示手上序数为i的牌的数量）
  188. - 从1到n枚举所有牌加到手牌中
  189. - 从1到n枚举对子
  190. - 从1到n枚举判断能否组成3m对刻子或者顺子

  192. 同时最后一步中我们可以发现 当我们能组成刻子的时候 就可以直接直接组一个刻子

  194. 于是这道题就十分简单的解决掉了

  196. 其时间复杂度为$O(n?)$



  200. ### 0x03 贪心

  202. 实际上来说 贪心并不算是一种算法 而是类似于一种思想

  204. 有一类问题会让我们求对于给定的输入数据的最优解之类的东西

  206. 我们称最后的答案为**全局最优解**

  208. 比如说这道题

  210. [纪念品分组]()

  212. 题目大意：

  214. 给定$n$个数和一个常数$k$

  216. 你需要将这$n$个数分成任意组 每组的和都需要小于等于$k$并且每组的数的个数不多于$2$

  218. 求最少的组数

  220. $n\le3\times10^4$



  224. 我们有一个显而易见的思路

  226. 枚举每一个数分到哪一组

  228. 但是更显而易见的是这么做又难写又跑得慢

  230. 于是我们可以想想别的做法

  232. 所以你把这一堆数排序后 把每一对尽可能小的值和尽可能大的值分成一组

  234. 之后再统计一下分了多少组就行了 复杂度$O(nlogn)$

  236. 但我们还没有严格的讨论这个做法的正确性 也就是说很有可能这个做法是**错误的**

  238. 不过  这个做法是没有错的 具体的证明在这里就略过了 有兴趣可以看题解



  242. 在这个题中 我们在每一次选择分组的时候都选择了对**当前**状态来说最优秀的选择

  244. 我们做出的选择被称为**贪心策略**

  246. 一个优秀的贪心策略是应当能从**当前**最优选择来推导出**全局**最优解的
  247. （也就是说,我们姑且认为下一步拿到的就是最好的,先拿到一个结果再说）

  249. 当然 也有可能有不存在满足上面这个条件的贪心策略的时候

  251. 这时候就说明这道题不可以用贪心解决

  253. 大多数贪心都有这样的过程： 首先给出一个感觉是对的的贪心策略 然后证明这个策略确实是对的

  255. 然而一般来说证明的过程总要比想出策略难很多

  257. 因此一般会以找反例的方式证明一个策略的正确性 找不到就是没有错

  259. 错误的贪心一般都会对某些特殊的输入数据得到错误的答案 于是我们可以构造反例来证明一个做法是错误的 这也是证明一个贪心做法错误的时候常用的方法



  263. ### 0x04 排序

  265. 在这一部分中 我们默认待排序的为$A$ 排序方式为升序排序



  269. #### 0x05 选择排序

  271. 选择排序是我认为最简单易懂的一种排序做法

  273. 其本质就是不断从数组中选择最小值放到最前面

  275. 选择排序需要确定$n$个位置 每次确定一个位置需要$O(n)$的时间扫一遍$A$

  277. 于是其复杂度为$O(n?)$

  279. 当你需要进行选择排序时 你只需要每次选择$A$中的最小元素 放到数组的最前面 然后再对剩下的$n-1$个数排序即可

  281. ```cpp
  282. for(int i=1;i<=n;i++){
  283.     int pos = i;
  284.     for(int j=i;j<=n;j++)
  285.         if(A[j] < A[pos])pos = j;
  286.     swap(A[i],A[j]);
  287. }
  288. ```

  290. #### 0x06 插入排序

  292. 插入排序也是一种比较易于理解的排序做法

  294. 我们可以在数列$A$外再定义一个数列$B$

  296. 将$A$从1到n遍历后 把每个$A_i$插入到$B$中合适的位置 同时满足B依然有序

  298. 最后的结果就是$B$

  300. 很明显的对于每一个$A_i$ 你都需要遍历一次$B$来找到适合它的位置

  302. 于是这个算法的复杂度也是$O(n?)$的

  304. 有必要说明的是,在数据序列较小的时候(N<=15),插入排序优于快排

  306. 代码太长 不在这写了

  308. #### 0x07 冒泡排序

  310. 冒泡排序的每一趟操作会从1到n扫一遍 并且将构成满足$A_i>A_i+1$的两个数交换

  312. 接下来我们证明当某一趟操作中没有交换任何数时 这个序列是有序的

  314. 首先我们发现：

  316. 当$A_i>A_j,i<j-1$ 并且对于任意的$k\in(i,j)$ 满足$A_k<A_j$ 那么同时有$A_i>A_k$

  318. 也就是说只要$A$中仍然存在$A_i>A_j,i<j$ 就一定会在下一趟操作中交换至少一次

  320. 之后我们会发现每一次交换后 满足$i<j,A_i>A_j$的$(i,j)$的对数一定会减少

  322. 当这个值减少到0时 这个数组显然就是有序的了 同时由上文可知 当存在$(i,j)$时 就一定会进行交换 于是冒泡排序的正确性得证

  324. ```cpp
  325. bool flag = true;
  326. while(flag){
  327.     flag = false;
  328.     for(int i=1;i<n;i++)
  329.         if(A[i] > A[i+1]){
  330.             flag = true;
  331.             swap(A[i],A[i+1]);
  332.         }
  333. }
  334. ```

  336. #### 0x08 桶排序

  338. 桶排序一般用于大量元素相对均匀分布的场合,这里只讲最简单的桶排序 也就是说只能排序非负整数

  340. 我们可以开一个数组$B$ 其中$B_i$表示在原数列中$i$出现的次数 我们认为每个$B_i$是一个桶

  342. 我们首先可以用$O(n)$的时间把$B$建出来

  344. 之后再从0到$maxA_i$ 枚举 把每个桶里的元素拿出来 最后得到的数组就是有序的

  346. 尽管看起来这个算法的复杂度是$O(n)$的 但是实际上你会发现最后一步导致了这个算法的复杂度为$O(n+maxA_i)$ 同时其空间复杂度也是$O(maxA_i)$

  348. 在$maxA_i$十分大时 时空复杂度都不可以接受

  350. ```cpp
  351. int B[n],maxA=0;
  352. for(int i=1;i<=n;i++)++B[A[i]],maxA=max(maxA,A[i]);
  353. for(int i=0,j=1;i<=maxA;i++)
  354.     while(B[i]--)A[j++] = i;
  355. ```



  359. 实际上这个算法在经过优化后是一个十分优秀的时空复杂度均为$O(n)$的算法

  361. 它的名字是基数排序 但是这并不在我们的讨论范围之中

  363. #### 0x09 归并排序

  365. 归并排序实际上是基于分治的思想来进行的排序

  367. 首先我们可以用$O(n)$的时间来合并两个**有序**的数列

  369. 于是我们可以认为对于其中的每个元素$A_i$ 是可以在$O(1)$的时间内进行合并的

  371. 那么我们可以将原数列分成两个数列$A_1\to A_{mid},A_{mid+1}\to A_n$

  373. 之后我们使用双指针i,j分别指向两个数列A,B的列头元素,比较元素大小,小者移动到

  375. 新数列中,与此同时被移动元素的数列,指针移动到下一个元素递归比较,直至某一数组

  377. 为空, 最后再合并起来得到一个有序的数列



  381. 对于这个算法 我们需要证明的是其复杂度为$O(nlogn)$

  383. 我们将算法的递归树建出来![img](https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/c0%3Dbaike92%2C5%2C5%2C92%2C30/sign=236fa62859b5c9ea76fe0bb1b450dd65/c8177f3e6709c93d673b9ed49d3df8dcd00054c3.jpg)

  385. 很明显的 在分解部分我们有一个深度为$logn$的递归树

  387. 那么这就意味着每一个元素$A_i$都会被合并$logn$次

  389. 于是对于$n$个元素 总共的合并次数就应当是$nlogn$的

  391. 同时每次合并的代价是$O(1)$ 于是归并排序的复杂度为$O(nlogn)$



  395. 代码太长

  397. #### 0x0A 快速排序

  399. 看名字就知道这个排序很快

  401. 但是依然还是$O(nlogn)$的 甚至最劣还能达到$O(n?)(最坏情况极难出现)$

  403. 对于每一趟操作,为了避免以前的排序结果(或者反序)带来的坏影响,

  405. 我们首先应用“三数中值分割法”,随机取三个数(例如数组开头,末尾和中位)取中值

  407. 选择一个枢纽元$A_i$ 然后将数列分为三部分 $B,A_i,C$

  409. 满足$\forall x\in B,x\le A_i$并且$\forall x\in C,A_i< x$

  411. 我们选定枢纽元之后,应该将其放到数组末端,然后采取双指针(i指向第一个元素,j指向倒数第二个元素)相向而行,

  413. 若是遇到比枢纽元“大”的元素,将其移动到右边,比枢纽元“小”的元素移动到左边,直至i,j交错

  415. 然后将枢纽元与最后一次右移的值交换

  417. 之后再对$B,C$分别进行快速排序



  421. 复杂度可以参考网上的资料 这里不再做证明

  423. #### 0x0B sort

  425. 大部分编程语言提供的库中都会有排序的函数 直接调用就好了(例如Java的Timsort算法和Array.sort)

  427. 这是我最推荐的一种排序方式
复制代码

#1.zip (6.37 KB, 下载次数: 1)