
数据结构与算法教程之入门(1)——常见算法技巧与思想
前言
这个系列的教程主要针对于 C/C++(或者其它差不多的语言)语法掌握基本到位的同学,但并不是不建议正在学习语法的同学同步学习。相反,我们其实提倡将算法学习与语法学习相结合,达到一个任务驱动的效果。
这里的算法与数据结构主要还是比较简单基础的一些,对于一些竞赛向的算法数据结构(比如各种动态规划优化、线段树相关、各种平衡树)可能涉及较少,在非常后面可能会选取极少而实用的一部分讲解。
同时,不要轻视这些基础的算法,其实在现实应用中,它们的使用频率远远高于前面所说的“高级”算法与数据结构。
常见的一些算法技巧与思想
首先,我们先来了解一下常见的算法相关思想。
这篇教程可能会根据后面的进度不断更新。
二分法
应用背景
在解决问题时,经常会遇到最大最小的问题,但是直接求解一个复杂问题的最值往往不是特别容易,但可能判断一个值是否能被达到(取到)会相对容易一些。
也就是说,二分最大的作用就是将求值类问题转换为判断型问题。
实例
- 高中数学可能学过,用二分法计算一个无理数比如 √2 的小数点若干位,我们难以直接计算 √2 的具体数值,但对于一个数 x,我们可以通过判断 x2 与 2 的关系,得知 x 与 √2 的关系,进而选择变大或者变小。同理,这种方法也被应用在了计算一段单调变号函数的零点过程中。
在查找算法中,我们经常需要查找一个元素在有序数列中的位置。这时我们直接通过值得比较、扫描往往需要较高的复杂度(最坏要扫描整个序列一遍),但是如果仅是判断某个位置元素跟查找的元素的大小关系(顺序),就会容易很多。这也就是经常所说的二分查找。详见语法教程第六章习题第三题。
最后举个与其他算法结合的例子:
数轴上有 n 个点,需要你选取 c 个点,使得其两两距离的最小值尽量大,求这个最大的最小距离。
跟别的算法结合的题往往具有需要求得最小的最大值,或者最大的最小值的特点。这时可以通过二分定一个最小距离的下界 d,保证两两距离必须小于等于 d,然后看看是否可以取到超过 c 个点,如果可以,说明最小的最大值至少为 d,否则就是小于 d。
具体算法过程
二分法首先要求对答案或者说所求的值,有一个上下界的范围。
这个范围可以很大,比如在 int
范围内,就是 −2147483648∼2147483647。
我们设当前的范围下界为 l,上界为 r,那么每次取定其中间值 mid = (l+r)/2
。
这里的 /
可能是整除也可能是浮点除,根据题目范围而定。
不妨假设想求取的是最大值,那么如果判断 mid 可以被取到,则说明最大值 ≥mid,所以将 l 移到 mid 重复过程;反之就将 r 移到 mid 继续进行。
代码实现
以求最大值为例。
下面这个是整型版,也就是所求的值为整数:
下面是浮点型版:
复杂度分析
对于整型版本,时间复杂度是 O(log(R−L))。
对于浮点型版本,则是 O(log(R−Leps))。
证明就略去了,相比大家也都会。
(对于时间复杂度不了解的,简单来说就是程序运行的次数,这里的 O 跟微积分笔记中的大 O 记号趋向于无穷时的含义基本相同。还是不懂可以私聊我)
相关习题
这里就直接给出别人的做题单。
三分法
应用背景
名字与二分法极其相似,但是既然是三分法,必然又不一样的地方。
三分的直接作用是计算单峰函数(数列)的极值,也就是山顶(谷)值。
算法实现与理论支持
首先还是需要答案的上下界范围 l 和 r,还是假设所求为最大值(峰顶),那么值应该先增后减。
然后我们在这之间取两个点,比如 mid1=l+(r-l)/3,mid2=r-(r-l)/3
。(整型情况的边界可以自己考虑一下)
然后计算 mid1 和 mid2 的值,如果 val(mid1)<=val(mid2),说明峰顶一定在 [mid1,r] 区间内;反之峰顶一定在 [l,mid2] 区间内。
可能的情况
(可能比例不太像,但大致理解一下)
代码实现
一种可能的实现:
浮点型的写法不再重复,可以自己钻研。
复杂度分析
同二分法,不解释。
特别地,有一种常数较小(大概就是同阶无穷大中系数较小的)的方法是利用斐波那契类似性质的写法,可以让每次 mid1 和 mid2 只有一个需要计算,想要学习的可以自己尝试或者查询。(当然,往往是没有必要的)
相关习题
给出一个二次函数的系数 a,b,c 和一个点 P(x,y),用三分法求 P 到二次函数对应抛物线的最小距离。
离散化
应用背景与实例
当一个数列的数值较大,但相关的状态却只与它们的值有关时,我们就需要离散化减少空间复杂度。
在动态规划(之后讲解)中,可能会有类似这样的状态:dp[i][j] 表示选取 i 个数,其中最大值为 k 的某个值。
这里如果 a[i] 的值较大,可能导致空间复杂度难以存储。
但实际上我们数组第二维中,实际上只需要 a[1] 到 a[n] 的值即可。
所以我们可以将这些值对应到 1 到 n 上,使得第二维复杂度变为 O(n)。
具体算法过程
首先将数列(数组)中的这些数值排序,一般就是从小到大,储存在数组 b 中。
然后对于 a[i],查找其在 b 中位置 pos,用 pos 代替原来的 a[i] 成为它的新值。
如果想要用到 x 对应的真实的值,只需要调取 b[x] 即可。
代码实现
复杂度分析
排序和查找时间复杂度相同,故为 O(nlogn)。
选做题
需要测试可以找人(比如作者)帮你出数据。
位运算
位运算是一种非常实用的思想与方法,但实现较为灵活,故这里只是大致举例讲解一下思想,之后具体算法遇到时会细讲。
应用举例
如何表示一个 n 元集合的子集?
我们可以通过一个 n 位二进制来表示,第 i 位 1 表示 a[i] 存在于子集中,0 表示不存在。
那么集合的交、并、对称差就能分别用 &
、|
、^
表示。
具体来说,我们可能会在树状数组、集合卷积以及线性基中多处使用。
这里最后举一个特别的例子:
有 2n−1 个数,其中 n−1 对两两相同,求那个孤立出来的一个数。(或者说有奇数个的那个)
比如 2,3,2,4,2,3,4 中孤立的就是 2。
这道题就可以利用异或运算 a^a=0
的性质,将 2n−1 个数异或起来,得到的就是孤立的数。
No Comments