数据结构与算法教程之入门(1)——常见算法技巧与思想

数据结构与算法教程之入门(1)——常见算法技巧与思想

前言

这个系列的教程主要针对于 C/C++(或者其它差不多的语言)语法掌握基本到位的同学,但并不是不建议正在学习语法的同学同步学习。相反,我们其实提倡将算法学习与语法学习相结合,达到一个任务驱动的效果。

这里的算法与数据结构主要还是比较简单基础的一些,对于一些竞赛向的算法数据结构(比如各种动态规划优化、线段树相关、各种平衡树)可能涉及较少,在非常后面可能会选取极少而实用的一部分讲解。

同时,不要轻视这些基础的算法,其实在现实应用中,它们的使用频率远远高于前面所说的“高级”算法与数据结构。

常见的一些算法技巧与思想

首先,我们先来了解一下常见的算法相关思想。

这篇教程可能会根据后面的进度不断更新。

二分法

应用背景

在解决问题时,经常会遇到最大最小的问题,但是直接求解一个复杂问题的最值往往不是特别容易,但可能判断一个值是否能被达到(取到)会相对容易一些。

也就是说,二分最大的作用就是将求值类问题转换为判断型问题

实例

  1. 高中数学可能学过,用二分法计算一个无理数比如 $\sqrt{2}$ 的小数点若干位,我们难以直接计算 $\sqrt{2}$ 的具体数值,但对于一个数 $x$,我们可以通过判断 $x^2$ 与 $2$ 的关系,得知 $x$ 与 $\sqrt{2}$ 的关系,进而选择变大或者变小。同理,这种方法也被应用在了计算一段单调变号函数的零点过程中。

  2. 在查找算法中,我们经常需要查找一个元素在有序数列中的位置。这时我们直接通过值得比较、扫描往往需要较高的复杂度(最坏要扫描整个序列一遍),但是如果仅是判断某个位置元素跟查找的元素的大小关系(顺序),就会容易很多。这也就是经常所说的二分查找。详见语法教程第六章习题第三题。

  3. 最后举个与其他算法结合的例子:

    数轴上有 $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]$ 区间内。

可能的情况

1-1

1-2

(可能比例不太像,但大致理解一下)

代码实现

一种可能的实现:

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$ 个数异或起来,得到的就是孤立的数。

 

点赞 2

No Comments

Add your comment