比较排序与计数排序时间复杂度的证明

比较排序

对于任意的比较排序算法,我们都能将其操作抽象成一颗决策树,这是一颗完全二叉树,它表示了某一排序算法对所有元素的比较操作。下图是插入排序的例子:
批注 2019-09-04 010631.jpg

每一条路径都是一种可能性,所以算法的最坏情况下的排序次数就是决策树的高度。

n个元素,可能的排序结果有A(n,n-1)=n!种,假设此时的树高为h,则叶子节点最多为2^(h+1)

2^(h+1) ≥ n!  
h + 1 ≥ log2(n!)

log(n!) = O(nlogn)

证明:

不等式缩放

log(n!) = log1 + ... + logn ≥ n/2 * log(n/2) = n/2 * logn - n/2 = c1 * logn
log(n!) = log1 + ... + logn ≤ nlogn = c2 * logn

Stirling 近似

76029ac06006a23f29011873c13a7a64541c6acd.svg

a35e8e0205988cf8552eec558d121f764d7e4021.svg

计数排序

计数排序的思想是:在待排序序列中,如果我们能统计出有多少元素小于或等于某一个元素,我们也就知道了该元素的正确位置。
例如:有五个元素小于x,那么就把x放到第六位(对于相同的元素我们认为最早遇到小于后面遇到的)。

实现该算法我们需要三个数组,初始input,结果output和表示元素统计数的count数组。
下面为算法的伪代码:

count = array of k+1 zeros
for x in input:
   count[key(x)] += 1

total = 0
for i in 0, 1, ... k:
   count[i], total = total, count[i] + total

output = array of the same length as input
for x in input:
   output[count[key(x)]] = x
   count[key(x)] += 1

return output

算法可视化

时间复杂度分析:假设在[0,k]的n个元素,数组初始化O(k),构造统计数组C是O(n),统计数累加O(k),排序是O(n)
所以总共时间复杂度为O(k+n)

计数排序是一种典型空间换时间的算法。

性能比较

下面是JS中的性能对比:

Array with 10000000 elements:
n log(n) takes 15.611 seconds
Linear takes 3.896 seconds

参考文章:
https://medium.com/free-code-camp/my-favorite-linear-time-sorting-algorithm-f82f88b5daa1

矩阵相乘的Strassen's算法

矩阵乘法的数学表达式为equation.png

对于两个n*n整数矩阵,相乘需要进行n^3次整数乘法和n^3-n^2次整数加法,显然时间复杂度为O(n^3)

我们先将问题简化,任意的矩阵乘法我们都可以转换为两个2x2的矩阵相乘。而这个2x2的矩阵乘法可以拆解为如下形式。
捕获.PNG

Strassen有(7/8)n^3次整数乘法和(7/8)n^3+(3/4)n^2+8次加法,而整数乘法运算时间大于加法。最终的时间复杂度为O(n*log2(7))

算法的核心思想是用更小规模的乘法来得到中间矩阵,最后加法汇总成需要的矩阵。

Introduction and Strassen’s Algorithm.pdf

JS 实现LRU缓存

为什么不直接用对象这种k-v结构,因为内存空间很宝贵而且是有限的。
在浏览器我们无所谓,但服务端就不一样了,例如nuxt就是用了LRU算法缓存接口数据或者渲染后的dom对象。

LRU(Least Recently Used)把最近没用过的一个置换出去,意思就是如果最近用到了就放到前面,如果不够了最后一个就是最近没使用的,将其删除掉就好。使用双链表就能满足这种需求。

/*
 * Illustration of the design:
 *
 *       entry             entry             entry             entry
 *       ______            ______            ______            ______
 *      | tail |.newer => |      |.newer => |      |.newer => | head |
 *      |  A   |          |  B   |          |  C   |          |  D   |
 *      |______| <= older.|______| <= older.|______| <= older.|______|
 *
 */
class Node {
    prev = null;
    next = null;
    constructor(k, v) {
        if (valid(k)) this.key = k;
        if (valid(v)) this.value = v;
    }

    valid(e) {
        return typeof key != "undefined" && key !== null
    }
}

class LRU {
    size = 0;
    head = null;
    tail = null;
    map = {};
    constructor(limit = 1000) {
        this.limit = limit
    }

    setHead(node) {
        node.next = this.head;
        node.prev = null;
        if (this.head !== null) this.head.prev = node;
        if (this.tail === null) this.tail = node;
        this.size++;
        this.map[node.key] = node;
    }

    set(k, v) {
        const node = new Node(k,v);
        if (this.map[key]) {
            this.map[key].value = node.value;
            this.remove(node.key);
        } else {
            if (this.size >= this.limit) {
                delete this.map[this.tail.key];
                this.size--;
                this.tail = this.tail.prev;
                this.tail.next = null;
            }
        }
        this.setHead(node);
    }

    get(k) {
        if (this.map[k]) {
            const value = this.map[k].value;
            const node = new Node(k, v);
            this.remove(k);
            this.setHead(node);
            return value;
        } else {
            console.log("Key " + k + " does not exist in the cache.")
        }
    }

    remove(key) {
        const node = this.map[key];
        if (node.prev !== null) {
            node.prev.next = node.next;
        } else {
            this.head = node.next;
        }
        if (node.next !== null) {
            node.next.prev = node.prev;
        } else {
            this.tail = node.prev;
        }
        delete this.map[key];
        this.size--;
    }
}

插入删除时间复杂度都是O(1)

现在为止我们实现了最为核心部分,但是缓存也不能无限的停留在内存中,像接口这些数据有时会发生改变,所以还需要为缓存加上有效期,在get时判断是否过期。

LRU能带给我们一定的收益,但是他也让我们的程序拥有了状态,也就不能做分布式来多实例负载均衡。

基于布隆过滤器的依赖注入

如果你读过Shadowsocks或者Angular的代码,你会发现他里面都自己实现了一个布隆过滤器。
SS用他来匹配GFW名单,Angular中用来依赖注入服务名单。NodeInjector是Ivy渲染器引入的Angular注入器,它大量使用bloom过滤器来检索令牌。

Bloom过滤器的基本数据结构是位向量。

Bloom Filter原理:当一个元素被加入集合时,通过K个Hash函数将这个元素映射成一个位阵列(Bit array)中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检索元素一定不在;如果都是1,则被检索元素很可能在。

Angular中的bloom比特位为256,因此我们有一个256位的向量,它被分成8个部分。

Angular 通过递增整数值生成(如果尚未定义)令牌的唯一ID,并将其置于静态__NG_ELEMENT_ID__属性。
它通过按位AND(&)运算符获取该数字并使其适合bloom大小,以便结果始终在0-255之间。

// 用原始 bloomBit 值决定检查那个 bloom 过滤器桶
// e.g: bf0 = [0 - 31], bf1 = [32 - 63], bf2 = [64 - 95], bf3 = [96 - 127], etc
const b7 = bloomBit & 0x80;
const b6 = bloomBit & 0x40;
const b5 = bloomBit & 0x20;
const tData = tView.data as number[];

if (b7) {
  b6 ? (b5 ? (tData[injectorIndex + 7] |= mask) : (tData[injectorIndex + 6] |= mask)) :
       (b5 ? (tData[injectorIndex + 5] |= mask) : (tData[injectorIndex + 4] |= mask));
} else {
  b6 ? (b5 ? (tData[injectorIndex + 3] |= mask) : (tData[injectorIndex + 2] |= mask)) :
       (b5 ? (tData[injectorIndex + 1] |= mask) : (tData[injectorIndex] |= mask));
}

代码都是位运算,看起来挺复杂,其实就是将2^bloomBit位置为1。下面是一个简单例子:

const bloomBit = 3 % 255 // 3
const mask = 1 << bloomBit;
             1 << 3 // 8
8..toString(2) // 1000
                           
1 bucket          00000000000000000000000000001000
....
8 bucket          00000000000000000000000000000000    

next_permutation 算法原理和JS实现

C++ STL中的 next_permutation 函数和 prev_permutation 两个函数提供了对于一个特定排列P,求出其后一个排列P+1和前一个排列P-1的功能。

我们假设一个序列Pn=<3 6 4 2>,我们可以从右起第一位看成各位,第二位为十位以此类推,那么很容易得出递减序列表示的数最大,这个例子中<6 4 2>为递减,已经无法通过交换数字位置得到更大的数,所以我们找到第一个非递减元素3,然后从前面递减序列中找到第一个大于它的元素4,交换着两个元素得到<4 6 3 2>,但是这里<6 3 2>仍是递减,而我们需要以4开头的最小序列,所以我们还要将递减序列颠倒成递增序列,最终得到Pn+1=<4 2 3 6>。

算法步骤如下:

  • 从尾端向前,找到两个相邻元素 i < (i+1)
  • 再从尾端向前,找到第一个元素满足 j > i
  • swap(i, j), 然后把 i+1 之后的所有元素 reverse 倒排
#include<cstdio>
#include<cstring>

void inline swap(char *s1,char *s2){
    char t=*s1;*s1=*s2;*s2=t;
}

//反转字符串函数,s,e分别执行字符串的开始和结尾
void reverse(char *s,char *e){
    for(e--;s<e;s++,e--)swap(s,e);
}

bool next_permutation(char *start,char *end){
    char *cur = end-1, *pre=cur-1;
    while(cur>start && *pre>=*cur)cur--,pre--;
    if(cur<=start)return false;
    
    for(cur=end-1;*cur<=*pre;cur--);//找到逆序中大于*pre的元素的最小元素 
    swap(cur,pre);
    reverse(pre+1,end);//将尾部的逆序变成正序 
    return true;
}

JS实现:

function next_permutation( arr ) {
    const length = arr.length;
    if( length <=1 ) return false;
    
    let i = length;
    while(true){
        var t = i;
        i--;
        if( arr[ i ] < arr[ t ] ) {
            var j = length;
            while( !( arr[ i ] < arr[ --j ] ) );

            const temp = arr[ i ];
            arr[ i ] = arr[ j ];
            arr[ j ] = temp;
            
            // splice()函数做了两件事,首先将arr的t以后的元素移除,并且将移除的部分颠倒后保存在rev中
            var rev = arr.splice( t, length ).reverse();

            // 将后面颠倒后的部分连接至arr,这里不能用concat()来连接,否则改变的就不是原来的arr了
            Array.prototype.push.apply( arr, rev );
            return true;
        }
        if(!i){
            arr.reverse();
            return false;
        }
    }
}