wzf2000 数据结构与算法教程之入门（1）——常见算法技巧与思想
Contents
前言
这个系列的教程主要针对于 C/C++（或者其它差不多的语言）语法掌握基本到位的同学，但并不是不建议正在学习语法的同学同步学习。相反，我们其实提倡将算法学习与语法学习相结合，达到一个任务驱动的效果。
这里的算法与数据结构主要还是比较简单基础的一些，对于一些竞赛向的算法数据结构（比如各种动态规划优化、线段树相关、各种平衡树）可能涉及较少，在非常后面可能会选取极少而实用的一部分讲解。
同时，不要轻视这些基础的算法，其实在现实应用中，它们的使用频率远远高于前面所说的“高级”算法与数据结构。
常见的一些算法技巧与思想
首先，我们先来了解一下常见的算法相关思想。
这篇教程可能会根据后面的进度不断更新。
二分法
应用背景
在解决问题时，经常会遇到最大最小的问题，但是直接求解一个复杂问题的最值往往不是特别容易，但可能判断一个值是否能被达到（取到）会相对容易一些。
也就是说，二分最大的作用就是将求值类问题转换为判断型问题。
实例
- 高中数学可能学过，用二分法计算一个无理数比如 $\sqrt{2}$ 的小数点若干位，我们难以直接计算 $\sqrt{2}$ 的具体数值，但对于一个数 $x$，我们可以通过判断 $x^2$ 与 $2$ 的关系，得知 $x$ 与 $\sqrt{2}$ 的关系，进而选择变大或者变小。同理，这种方法也被应用在了计算一段单调变号函数的零点过程中。
在查找算法中，我们经常需要查找一个元素在有序数列中的位置。这时我们直接通过值得比较、扫描往往需要较高的复杂度（最坏要扫描整个序列一遍），但是如果仅是判断某个位置元素跟查找的元素的大小关系（顺序），就会容易很多。这也就是经常所说的二分查找。详见语法教程第六章习题第三题。
最后举个与其他算法结合的例子：
数轴上有 $n$ 个点，需要你选取 $c$ 个点，使得其两两距离的最小值尽量大，求这个最大的最小距离。
跟别的算法结合的题往往具有需要求得最小的最大值，或者最大的最小值的特点。这时可以通过二分定一个最小距离的下界 $d$，保证两两距离必须小于等于 $d$，然后看看是否可以取到超过 $c$ 个点，如果可以，说明最小的最大值至少为 $d$，否则就是小于 $d$。
具体算法过程
二分法首先要求对答案或者说所求的值，有一个上下界的范围。
这个范围可以很大，比如在 int 范围内，就是 $-2147483648 \sim 2147483647$。
我们设当前的范围下界为 $l$，上界为 $r$，那么每次取定其中间值 mid = (l+r)/2。
这里的 / 可能是整除也可能是浮点除，根据题目范围而定。
不妨假设想求取的是最大值，那么如果判断 $mid$ 可以被取到，则说明最大值 $\ge mid$，所以将 $l$ 移到 $mid$ 重复过程；反之就将 $r$ 移到 $mid$ 继续进行。
代码实现
以求最大值为例。
下面这个是整型版，也就是所求的值为整数：
int Binary(int L,int R)
{
int l=L,r=R,Ans=L;//L 和 R 为给定的上下界，Ans 记录目前得出的最大值
while (l<=r)
{
int mid=(l+r)/2;
if (check(mid)) Ans=mid,l=mid+1;//check() 函数表示是否可以取到，如果可以就更新 Ans
else r=mid-1;//注意 l,r 的变化。
}
return Ans;//最终的 Ans 就是最大值
}
下面是浮点型版：
const double eps=1e-7;//这里的精度可以自己调节
double Binary(double L,double R)
{
double l=L,r=R;//L 和 R 为给定的上下界
while (r-l>=eps)
{
double mid=(l+r)/2.;
if (check(mid)) l=mid;//check() 函数表示是否可以取到
else r=mid;//注意 l,r 的变化。
}
return l;//改为 r 效果不变
}
复杂度分析
对于整型版本，时间复杂度是 $O(\log(R-L))$。
对于浮点型版本，则是 $O(\log(\frac{R-L}{eps}))$。
证明就略去了，相比大家也都会。
（对于时间复杂度不了解的，简单来说就是程序运行的次数，这里的 $O$ 跟微积分笔记中的大 $O$ 记号趋向于无穷时的含义基本相同。还是不懂可以私聊我）
相关习题
这里就直接给出别人的做题单。
三分法
应用背景
名字与二分法极其相似，但是既然是三分法，必然又不一样的地方。
三分的直接作用是计算单峰函数（数列）的极值，也就是山顶（谷）值。
算法实现与理论支持
首先还是需要答案的上下界范围 $l$ 和 $r$，还是假设所求为最大值（峰顶），那么值应该先增后减。
然后我们在这之间取两个点，比如 mid1=l+(r-l)/3,mid2=r-(r-l)/3。（整型情况的边界可以自己考虑一下）
然后计算 $mid1$ 和 $mid2$ 的值，如果 $val(mid1)<=val(mid2)$，说明峰顶一定在 $[mid1,r]$ 区间内；反之峰顶一定在 $[l,mid2]$ 区间内。
可能的情况
（可能比例不太像，但大致理解一下）
代码实现
一种可能的实现：
int Find(int l,int r)//这里以在一个凸性序列中查找元素为例
{
while (l<r)
{
int mid1=(l+r)/2,mid2=(mid1+r)/2;
if (val(mid1)<=val(mid2)) l=mid1;//val 函数表示获取值
else r=mid2;
}
return l;
}
浮点型的写法不再重复，可以自己钻研。
复杂度分析
同二分法，不解释。
特别地，有一种常数较小（大概就是同阶无穷大中系数较小的）的方法是利用斐波那契类似性质的写法，可以让每次 $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]$ 即可。
代码实现
int Discretization(int a[],int b[],int n)//含义同上
{
for (int i=1;i<=n;i++) b[i]=a[i];
sort(b+1,b+n+1);//可查看语法教程第四章查看相关含义
for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n+1,a[i])-b;//这里可以改为自己写的二分查找函数，lower_bound 的用法可以自己学习或者看一下语法教程第四章最后部分
return 0;
}
复杂度分析
排序和查找时间复杂度相同，故为 $O(n \log n)$。
选做题
需要测试可以找人（比如作者）帮你出数据。
位运算
位运算是一种非常实用的思想与方法，但实现较为灵活，故这里只是大致举例讲解一下思想，之后具体算法遇到时会细讲。
应用举例
如何表示一个 $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