倍增思想

倍增思想的核心是每次根据已经得到的信息,将考虑的范围扩大一倍,从而加速操作。

在变化规则相同的情况下加速状态转移

这里变化规则相同指的是:

  • 每次的变化规则必须相同
  • 变化规则必须满足结合律(加法,乘法)

我们考虑一下计算2的10次方,怎样算比较快?
最简单我们乘九次即可,但是每次只是乘2是不是太少了,如果乘以4,乘以8,那么计算的次数是不是就会少以些。我们可以先计算2*2,然后4*416*16,这样我们利用上一次计算的结果,步子越来越大,也就是我们向结果状态转移的速度越来越快,这就是倍增的基本思想。

递归快速幂,先计算a的n/2次方,然后平方;如果n是奇数,那么就先计算a的n-1次方,再乘上a;递归出口是a的0次方为1。

int qpow(int a, int n) {
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a;
    else
    {
        int temp = qpow(a, n / 2);
        return temp * temp;
    }
}

加速区间操作

稀疏表(Sparse Table)主要用来求解RMQ(Range Minimum/Maximum Query)区间最大/最小值查询问题。即给定一个数组,动态查询数组任意区间范围内的最小值。

我们使用倍增的思想预处理数据,定义一个二维数组 f,对于范围内的所有ST[i][j]表示被查询数组
$[j, j+2^i - 1]$区间的最小值。

我们首先初始化ST[0][j] = a[j],然后在长度为2的每个数组子范围中找到最小值,随后长度翻倍为4,依此类推。

img
img

在计算这个ST数组时,我们可以使用动态规划重用状态。

$ST[i][j]=min \left\{\begin{aligned} ST[i][j-1] \\ ST[i+2^j-1][j-1]\end{aligned}\right. $

img
例如:ST[2][3] = min(ST[1][3], ST[1][5])

查询时我们先计算 $k = \left \lfloor\log_2 (r-l+1) \right \rfloor$ 然后将区间拆分为[r, k-1]和[k, l],然后再ST数组上查找即可。

预处理的复杂度为O(nlogn),之后查询只需要O(1)时间。稀疏表的主要缺点是输入数组无法更改。任何更改都将需要新的预计算来恢复数据结构。如果需要在变化的数组中回答最小或最大范围查询,则最好使用段树。

const int MAXN = 105000;
const int MAXLOG = 20;

int n;
int a[MAXN];
int table[MAXLOG][MAXN];

void buildSparseTable() {
  for (int i = 0; i <= logs[n]; i++) {
    int curLen = 1 << i; // 2^i
    for (int j = 0; j + curLen <= n; j++) {
      if (curLen == 1) {
        table[i][j] = a[j];
      } else {
        table[i][j] = min(table[i - 1][j], table[i - 1][j + (curLen / 2)]);
      }
    }
  }
}

int getMin(int l, int r) {
  int p = logs[r - l + 1];
  int pLen = 1 << p; // 2^p
  return min(table[p][l], table[p][r - pLen + 1]);
}

此外LCA,和后缀数组都能应用到倍增思想。

为何二倍增

假设为K增,那么相关系数$ \log_2N $就变成了$(k-1)\log_kN$(因为预处理时要向后取用(k-1)个已知结果才能将范围扩大为原来的k倍),显然这个函数是单调递增的,所以只有在k为2时复杂度最低。

参考文章

http://adilet.org/blog/sparse-table/
https://oi-wiki.org/ds/sparse-table/
https://zhuanlan.zhihu.com/p/95902286
https://wenku.baidu.com/view/33219414a6c30c2259019e54.html

生日悖论(Birthday paradox)

考虑一个问题,平均在多少人中才能找到一对相同生日?

答案是23人。

换一个角度,如果你进入了一个有着23个人的房间,房间里的人中会和有相同生日的概率便不是50:50了,而是变得非常低。原因是这时候只能产生23种不同的搭配。根据下面概率公式,只有n=253时,能让某人生日与我相同的概率为1/2。
$\begin{aligned} y=(1-\frac{1}{365})^n\end{aligned}$

生日问题实际上是在问任何23个人中会有两人生日相同的概率是多少,也就是说没有特定人选
$\begin {aligned} y=1-\dfrac {365!}{365^{n}\left( 365-n\right) !}\end{aligned}$

比较这两者曲线,第二种的增长非常快:

v2-b8a148d4e4221cf34b22aa28281d0e24_720w.jpg

#include<stdio.h>  
int main()  
{  
    int T,n,i;   
    scanf("%d",&T);  
    int k=0;  
    while(T--)  
    {  
        scanf("%d",&n);  
        double p=1.0;  
        int num=0;  
       for(i=0;; i++)  
       {  
          p=p*(1-(double)i/n);  
           num++;  
          if(1.0-p>=0.5)  
            break;  
       }  
        printf("Case %d: %d\n",++k,num-1);  
    }  
    return 0;
}
  

应用

Pollard’s Rho整数因子分解算法

假设 𝑵 是一个能被分解为 𝒒 ∗ 𝒓 的数 ( 𝑵 = 𝒒 ∗ 𝒓 且 𝒒 ≠ 𝒓 )
我们的目标是找到 𝑵 的其中一个因子 𝒒 或 𝒓 (另外一个因子可以通过除 𝑁 来得到 )

最传统的方法是试除法

let N = 29;                    
let flag = 1;                   
if(N % 2 == 0) flag = 0;                 //首先测试 N 是否是偶数
else for(let i = 3;i * i < N;i += 2){    //与刚才不同的是,我们先从 3 开始,每次增加 2,一直
                                         //到根号下 N 为止。这样我们的测试就在奇数中展开
    if(N % i == 0){            
        flag = 0;
        break;                 
    }
}

我们随即地从[1,N]中选择一个数,这个数是 p 或者 q 的可能性是非常小。但是我们可以转换角度,不再只选取一个整数,我们能够选取 k 个数,然后在这k个数中寻找是否存在a − b 能够整除 𝑁。这样我们就将概率从我们可以将可能性从 1/𝑁 提高到 √1/𝑁
做差之后等于p或q,只有两个还是太少了,我们可以还可以更进一利用最大公约数gcd(|a - b| ,N) > 1,满足这个条件的就多了𝑞,2𝑞,3𝑞,4𝑞,……,(𝑟 − 1)𝑞,𝑟,2𝑟,3𝑟,4𝑟,……,(𝑞 − 1)𝑟一共有𝑞 + 𝑟 − 2 个数,到现在我们只需要大约 $N^(1/4) $ 个数。

在实际计算时,我们不预先生成随机数,而是一个一个地生成并检查连续的两个数。

// 随机数生成
function g (x, prime) {
  return (Math.pow(x, 2) + 1) % prime
}

// 最大公约数
function gcd (a, b) {
  if (!b) return a;
  return gcd(b, a % b)
}

function pollardRho (prime) {
  let x = 2;
  let y = 2;
  let d = 1;

  while (d === 1) {
    x = g(x, prime);  //x runs once
    y = g(g(y, prime), prime); ; //y runs twice as fast

    d = gcd(Math.abs(x - y), prime);

    if (d === prime) return;
    if (d !== 1 && !isNaN(d)) return d;
  }
}

哈希碰撞

我们以CRC16 为例,哈希值是17位,2 ^ 8 = 256 个项目的集合中,哈希冲突的机率就会达到约为50%。
这里是CRC16-CRC64的测试 1

安全的Hash标准的输出长度选为160比特是出于这种考虑。

参考文章

http://www.math.umbc.edu/~campbell/NumbThy/Class/Programming/JavaScript/
https://www.cs.colorado.edu/~srirams/courses/csci2824-spr14/pollardsRho.html
https://wenku.baidu.com/view/c3e3657b27284b73f24250d5.html

Boyer-Moore多数表决算法

问题陈述

假设你有一个未排序的值列表。你想知道列表中是否存在该列表中一半以上元素的值。如果有则这个值是什么?尽可能高效地完成此任务。

出现此问题的一个常见原因可能是容错计算。执行多个冗余计算,然后验证大多数结果是否一致。‘

简单的解决方案

简单的解决方案是哈希表。时间复杂度是O(N),空间复杂度是O(N)。

Boyer-Moore多数表决算法

首先检查该count值。如果计数等于0,则将设置candidate为当前元素的值。接下来,首先将元素的值与当前candidate值进行比较。如果它们相同,则增加count1。如果它们不同,则减少count1。

candidate = 0
count = 0
for value in input:
  if count == 0:
    candidate = value
  if candidate == value:
    count += 1
  else:
    count -= 1

最终 candidate 即为众数,该算法空间复杂度是O(1)。

我们用下面一组数据来理解,我们把 5 看成 -1 ;0 看成 +1 ,只要不同就相互抵消,相同的元素相加,多的一方一定会把另一方抵消掉。下面是计算过程:

[5, 5, 0, 0, 0, 5, 0, 0, 5]

[1, 2, 1, 0, 1, 0, 1, 2, 1]  // count 取值

[5, 5, 5, 5, 0, 0, 0, 0, 0]  // candidate 取值

推广

每次删除三个不相同的数,最后留下的可能是出现次数超过1/3的数,这个思想可以推广到出现次数超过1/k次的元素有哪些。需要注意的是最后还需要再遍历一遍结果,判断次数最多和次多的是不是超过了⌊ n/3 ⌋次。

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int m = 0, n = 0, cm = 0, cn = 0;
        for (int i : nums) {
            if (m == i) {
                ++cm;
            } else if (n == i) {
                ++cn;
            } else if (cm == 0) {
                m = i;
                cm = 1;
            } else if (cn == 0) {
                n = i;
                cn = 1;
            } else {
                --cm;
                --cn;
            }
        }
        cm = cn = 0;
        for (int i : nums) {
            if (i == m)
                ++cm;
            else if (i == n)
                ++cn;
        }
        vector<int> res;
        const int N = nums.size();
        if (cm > N / 3)
            res.push_back(m);
        if (cn > N / 3)
            res.push_back(n);
        return res;
    }
};

并行计算

Finding the Majority Element in Parallel

以 [1, 1, 1, 2, 1, 2, 1, 2, 2] 为例,我们可以将其拆开。

分组1:
[1, 1, 1, 2, 1]
candidate = 1
count = 3

分组2:
[2, 1, 2, 2]
candidate = 2
count = 2

可以将第1部分的结果视为与[1,1,1]相同,而将第2部分的结果视为与[2,2]。

参考文章:

https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html

一种使用倒排索引和位图的快速SKU选择方法

使用所有有货的SKU组合生成该SKU到该组合的索引。如 [A-B,B-C] 即生成 {A:[1],B:[1,2],C:[2]}
映射到视图时只需要判断当前选中项的SKU索引的交集(默认为全集),例如选中B,则[1,2,3][1,2]的交集[1,2],然后依次遍历SKU,判断SKU对应的索引与当前选中索引是否有交集。如果有则可选,没有则置灰。

索引可以使用位图数据结构,在判断是否为交集使用位运算提升性能。

   const sku = [];
    const revertIndex = {};
    const size = 8;
    // 随机sku
    for (let i = 0; i < size; i++) {
        sku[i] = new Set();
        for (let j = 0; j < size; j++) {
            const v = j * size + RandomNumBoth(0, size);
            sku[i].add(v)
        }
    }

    for (let i = 0; i < sku.length; i++) {
        sku[i].forEach((e) => {
            if (!revertIndex[e]) revertIndex[e] = 0;
            revertIndex[e] |= 1 << i
        })
    }

判断是否选中使用 (revertIndex[(line-1)*size + e -1] & union)

下面是一个简单的例子,取消选择和选中逻辑是一样的,所以就暂时没写:

See the Pen SKU Demo by zhangchen (@zhangchen915) on CodePen.

不相交集合元素的数据结构——并查集

不相交集合有两种基本操作:合并(union)和查询(find)。

并查集保持了一组不相交的动态集合,每个集合通过一个代表来识别,代表即集合中的某个成员。

数组实现Quick Find

我们可以直接用数组来存储集合的标识,这样查找操作直接返回对应数组的值即可,复杂度为O(1);而合并操作每次都需要遍历整个数组,复杂度为O(n)

     0   1   2   3   4   5   6   7   8   9
     -------------------------------------
 id  0   1   2   3   4   5   6   7   8   9

union(1, 4)
union(1, 5)

     0   1   2   3   4   5   6   7   8   9
     -------------------------------------
 id  0   1   2   3   1   1   6   7   8   9

有根树表示 Quick Union

为了降低合并操作的复杂度,我们可以用多个有根树表示集合,每个结点存储指向其父亲结点的指针,根节点指向自己。判断是否属于同一个集合时,我们只需要判断元素所属的树根是否相同。

批注 2019-10-08 010040.jpg

这种方式实际上并没有本质提高,而且如果一些极端情况下会退化成一个链表,查找操作的复杂度反而上升了,上面的例子中就是这样。

查找和合并的时间复杂度都为O(h),h表示树高。

所以我们需要对合并操作进行优化,优化方式一般为以下两种。

按秩合并(union by rank)

秩(Rank)就是一颗树的结点数,即使包含较少结点的树根指向包含较多结点的树根。
所以上面的例子中union(1, 2)操作会让 2 节点会指向 1 。
批注 2019-10-08 010145.jpg

这样查找操作最坏情况的时间复杂度为O(logN)

路径压缩

在查找所在位置是我们会进行递归,那么我们可以利用递归回溯的过程进行路径压缩。所谓压缩表示的就是将从x结点搜索到祖先结点所经过的结点都指向该树的根节点结点。
DSU_path_compression.png

在压缩之后树的高度低了,所以查找复杂度也降低了。

同时使用按秩合并和路径压缩

复杂度为反阿克曼函数,具体的证明比较复杂,可以参科下面这篇讲义。
这里简单介绍下阿克曼函数,他表示f(n) = 2 ^2^2^…^2,可见其增长速度极快,其反函数用lg*n表示,其值可以认为小于5。

https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/UnionFind.pdf

批注 2019-10-08 010145.jpg
参考文章:
https://cp-algorithms.com/data_structures/disjoint_set_union.html
https://algs4.cs.princeton.edu/15uf/