导语

记得高中时，老师曾经出过一道题目，1000的999次方和999的1000次方谁大，凭直觉，很多人都说当然是999的1000次方更大，至于为什么，当时很少有同学知道，很多人都这样想的，底数相差1，次方大1的数更大。当年，老师带着大家做了深入的思考和分析，总结出来了规律和原因，结果证明直觉并不可靠。直至最近，我看到一个三进制计算机性能更好的视频，突然把这两个知识串联起来了，再此做一个分享

抽象&分析

当年老师首先要求我们进行题目抽象，1000^999，其实就是有999个1000相乘，这些数的和等于1000*999=999000，而999^1000，就是1000个999相乘，这些数的和也正好是999000，于是，题目就变成了把一个正整数拆成n个正整数的和，是它们的积最大？

那么如何解决抽象出来的问题呢，999000数字太大，不好拆解，那么就使用个小点的数字，比如12，12能怎么拆呢，无非下面几种情况：
12=1+1+1……+1，一共12个1相加，积为1
12=2+2+2……+2，一共6个2相加，积为64
12=3+3+3+3，一共4个3相加，积为81
12=4+4+4，一共3个4相加，积为64
12=5+5+2，积为552，积为50
……
还有其他拆解方法，但是显然，最大的就是拆解为4个3，这时我们就发现了，之前直觉并不对，为什么？因为2^6和3^4相比，次方数2^6比3^4大2，底数小1，但是最后的结果是3^4更大。不管你后面怎么拆，3^4的值最大。仔细看看拆分的方案，规律可以总结为：

1. 拆一个正整数为n个正整数相乘，尽可能地多拆3出来，不能拆3，就拆2或者4，坚决不能拆1；
2. 如果拆出来的数比3大的越多，乘积就越小，比如上面的4^3和5%2等比3大的拆分方案；
   知道了这个规律后，就非常容易判断1000^999和999^1000哪个数更大，显然，999比1000更接近3，999^1000更大。那么上面的规律如何证明呢，我记得老师噼里啪啦写了推导，证明过程如下：

N = x + x + …… + x，把大N拆成n个x的和，n=N/x，要使得f(x) = x^n=x^(N/x)最大。
如果要求f(x)最大，lnf(x)也满足最大，两边取对数lnf(x) = lnx^(N/x)，即lnf(x) = (N/x)*lnx。
求导数[lnf(x)]' = N * (1-lnx) / x^2，显然当x > e，导数小于0，是减函数，x < e，导数大于0，是增函数，所以x = e时，lnf(x)最大，e = 2.71818，显然最接近e的正整数就是3，所以规律得证。

联想

最近又看到一个视频，讲得是三进制计算机性能最好，我突然联想到这个曾经学过的知识，后来仔细想了下，视频想表达的观点，应该是三进制比二进制或者十进制表达能力更强，相同的内存大小，如果是三进制，可以表达的数最多。小时候都玩过一个游戏，一组珠串，假设给你100颗珠子，怎样分配，可以使得表示的数字数量最多，结果就是下图：

每个柱子上留三颗珠子，可表示3^324个数（计算机里面就是3^324个状态），表达的数量最多。没想到，三进制表达能力最强，在我高中时，老师就把原因告诉了我，哈哈。所以学好数学，培养好逻辑思考能力，真的是终身受用，加油吧，少年。

背景

记得在大学课程中，修过《算法和数据结构》，其中的0-1背包问题，是非常经典的算法题目，当时上课时，听老师讲完后，懂了个大概，工作若干年后，已经都忘记得差不多了，印象深刻的就是往背包里面塞东西，有个重量限制，问能取得的最大价值是多少。当时最naive的想法是，贪心不就完了，用价值/重量比最高的往里面塞就可以了，但其实这个贪心解法在0-1背包问题上是不work的。对于0-1背包问题，贪心选择之所以不能得到最优解是因为：它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。（原因引用出处）最近，我想看看0-1背包问题，到底有什么算法求解，是最合适的，也是最合理的，所以开始翻阅了资料，自己动手实现了代码，也就有了此文。

问题

说了这么多，在这篇文章中，您将看到以下内容：

1. 0-1背包问题的三种实现，时间复杂度和空间复杂度分析；
2. 针对上述的代码实现，构建实际测试用例，看实际case下的benchmark数据；

讨论

0-1背包问题（NP-Complete）

问题定义，给定N个物品，w[i]表示第i件物品的重量，v[i]表示第i件物品的价值。给你一个背包，总重量限制为W。求这个背包可以装下物品的最大价值和，注意，每个物品最多用一次。
解法1. 组合搜索
使用一个长度为n的二进制string，表示x0x1……xn。其中xi要么是0要么是1，0表示该物品不放入背包，1表示放入背包。尝试所有的可能组合。时间复杂度O(2^n),空间复杂度O(n)。该实现时间复杂度较高，一般只能在n很小的时候使用，一般为n <= 20，而且v,W >> 10^6。
代码实现如下：

func knapsack01C(v []int, w []int, W int) int {
    defer time_cost(time.Now(), "knapsack01C")
    r := 0
    var help func(s int, c_w int, c_v int)
    help = func(s int, c_w int, c_v int) {
        if c_v > r {
            r = c_v
        }

        for i := s; i < len(v); i++ {
            if c_w+w[i] <= W {
                help(i+1, c_w+w[i], c_v+v[i])
            }
        }
    }

    help(0, 0, 0)

    return r
}

解法2. 记忆化递归
定义dp(i,j)为使用前i个物品，在重量为j获取到的最大价值，dp(*,0) = 0。关键是把(i,j)看作一个状态(state)，这个state下最大的价值作为值记忆化存起来，再此求解到相同状态，直接返回之前求解的值即可。
举个实例：
v = {1, 2, 4, 5}
w = {1, 1, 2, 2}

解法2的时间复杂度，O(NW)，空间复杂度，O(NW)，如果重量w = {1, 2, 4, 8……, 2^n}，那么会退化为解法1，不会有上图中重复子问题的出现，可见记忆化递归和下面要讲的动态规划，都是基于问题是否存在大量的重复子问题，如果没有，意义不大。
代码实现如下：

func knapsack01R(v []int, w []int, W int) int {
    defer time_cost(time.Now(), "knapsack01R")
    n := len(v)
    dp := make(map[[2]int]int)
    var help func(i int, l_w int) int
    help = func(i int, l_w int) int {
        if i == 0 {
            return 0
        }

        k := [2]int{i, l_w}
        t, ok := dp[k]
        if ok {
            return t
        }

        l, r := 0, 0
        if l_w >= w[i-1] {
            l = help(i-1, l_w-w[i-1]) + v[i-1]
        }
        r = help(i-1, l_w)

        ret := 0
        if l > r {
            ret = l
        } else {
            ret = r
        }

        dp[k] = ret
        return ret
    }

    r := 0
    for i := 0; i <= n; i++ {
        t := help(i, W)
        if t > r {
            r = t
        }
    }
    return r
}

解法3. 动态规划
这个方式与方法2记忆化递归方法类似。
定义dpi为使用前i个物品，在重量为j时获取到的最大价值。状态转移方程：
dpi = dpi-1 j < w[i] or max{dpi-1]+v[i], w[i] <= j <= W}
ans = max{dpN}
时间复杂度为O(NW)，空间复杂度O(NW)。空间复杂度通过滚动数组，可以降维到O(W)。什么时候使用此解法？一般n > 20并且N、W在10^6~10^7数量级。
代码实现如下：

func knapsack01D(v []int, w []int, W int) int {
    defer time_cost(time.Now(), "knapsack01D")
    n := len(v)
    var dp [][]int
    for i := 0; i <= n; i++ {
        row := make([]int, W+1)
        dp = append(dp, row)
    }

    for i := 0; i <= n; i++ {
        dp[i][0] = 0
    }

    for j := 0; j <= W; j++ {
        dp[0][j] = 0
    }

    for i := 1; i <= n; i++ {
        for j := 0; j <= W; j++ {
            dp[i][j] = dp[i-1][j]
            if j >= w[i-1] && dp[i-1][j-w[i-1]]+v[i-1] > dp[i][j] {
                dp[i][j] = dp[i-1][j-w[i-1]] + v[i-1]
            }
        }
    }

    r := 0
    for i := 0; i <= W; i++ {
        if dp[n][i] > r {
            r = dp[n][i]
        }
    }

    return r
}

空间复杂度可以从O(NW)降低到O(W)，使用的是动态规划最常规的方案，滚动数组，注意复值的顺序，应该从数组尾端到头部赋值，代码如下：

func knapsack01D2(v []int, w []int, W int) int {
    defer time_cost(time.Now(), "knapsack01D")
    n := len(v)
    dp := make([]int, W+1)

    for j := 0; j <= W; j++ {
        dp[j] = 0
    }

    for i := 1; i <= n; i++ {
        for j := W; j >= w[i-1]; j-- {
            if dp[j-w[i-1]]+v[i-1] > dp[j] {
                dp[j] = dp[j-w[i-1]] + v[i-1]
            }
        }
    }

    r := 0
    for j := 0; j <= W; j++ {
        if dp[j] > r {
            r = dp[j]
        }
    }

    return r
}

性能测试的benchmark
虽然上述3种解法都是可以work的，但是在性能上差别颇大，并且解法1在物品数量N<10时(W为10^5~10^6)，耗时较动态规划和记忆化递归更小，但是随着N的变大，特别是N>20开始，极速衰减性能（果然和理论值匹配），具体benchmark性能图表如下：

结束

到这里，对经典0-1背包问题的讨论暂告一个段落，可以看到0-1背包作为一个NPC问题，算法时间复杂度还是比较高的，所以一般的搜索组合算法，现在在物品数量>20时，在实际工作中是不太可行的，这个递归搜索的代码实现，唯一的优势是，代码简单易懂。但到了这里，还是不够，我后面也想在深入思考下，0-1背包问题的2个变种问题，即unbounded背包和bounded背包，这两个问题会更复杂些，但基于0-1背包问题的讨论基础上，或许会更容易理解。

背景

蓄水池采样算法，用以解决在不确定数据量情况下的采样，比如数据流随机采样K个值，并且每一个值的采样概率需要相同，乍一听好神奇，怎么证明这个相同的概率是理论正确的呢？

证明过程

先附上一个自己的代码实现：

func reservoirSampling(sample int, total int) ([]int, int) {
    r1 := make([]int, total)
    r2 := 0

    for i := 0; i < total; i++ {
        r1[i] = i
    }

    for i := sample; i < total; i++  {
        tmp := rand.Intn(i)
        if tmp < sample {
            r1[i], r1[tmp] = tmp, i
        }
    }

    return r1[:sample], r2
}

这里并没有体现是一个数据流，但没关系，这个不影响采样概率的证明。证明的过程，如果是理解了问题的本质，其实比较简单，分两种情况讨论，假设从n个数据中随机采样k个数据：

1. 来看第1～k个数据，如果要保留到最后的采样集合中，一开始1~k保留的概率为1，直到k+1个数据出现，对于1~k个数据中任何一个数据来说，被选中换出的概率是1/(k+1)，反面就是被保留的概率，就是1-1/(k+1)=k/k+1，紧接着第k+2个数据来了，那么类似的分析法，被保留的概率是(k+1)/(k+2)，以此类推，知道第n个数据出现，概率就是(n-1)/n，前面分析的概率全部相乘，最终被保留的概率是k/n。
2. 来看第i个数据（i>k），第i个数据被选中的概率，显然是k/i，紧接着第i+1个数据来了，此时前面第i个数据被剔除的概率为1/(i+1)，被保留的概率就是1-1/(i+1)=i/(i+1)，第i+2个数据来了，类似的分析法，第i个数据被保留的概率是(i+1)/(i+2)，那么到第n个数据的时候，被保留的概率是(n-1)/n，前面分析的概率全部相乘，最终被保留的概率是k/n。
   完美证明，如论是最开始的1~k个数据，还是k+1~n个数据，选中被保留到最后的概率都是k/n，是不是很神奇？简单的数学，总是令人开心，不需要关心一堆复杂公式的推导，哈哈。

和naive随机采样的对比

其实蓄水池采样算法不仅仅可以用于数据流中随机取k个数据，也可以用在确定的n个数据中取k个不重复数据，写了一个naive的随机取k个数据，还要去重（因为随机取数据过程可能会重复），那么如果采样的数据量和整体比较大，比如3000个数要取1000个出来，蓄水池算法的性能比较好，而且代码实现上更加优雅，因为navie的随机取，需要考虑去重，不仅性能差，代码可读性也较差，如下：

func naiveSampling(sample int, total int) ([]int, int) {
    r1 := make([]int, sample)
    r2 := 0
    m := make(map[int]bool)
    for i := 0; i < sample;  {
        tmp := rand.Intn(total)
        if _, ok := m[tmp]; ok {
            // 不去重
            r2++ 
            // 去重
            // continue
        }

        r1[i] = tmp
        m[tmp] = true
        i++
    }

    return r1, r2
}

func randomSequence(sample int, count int, total int, f func(int,int)([]int, int)) {
    start := time.Now()
    rand.Seed(time.Now().UnixNano())

    m := make(map[int]int)
    r := 0
    for i := 0; i < count; i++ {
        r1, r2 := f(sample, total)
        r += r2
        for _, v := range r1 {
            m[v] += 1
        }
    }
    elapsed := time.Since(start)
    fmt.Printf("elapsed=%v\nr|t=%d|%d, rr=%f, sample=%d\nm=%v\n",
        elapsed, r, sample*count, float32(r)/float32(sample*count), len(m), m)
}

func main() {
    fmt.Printf("naiveSampling, sample=500, total=3000\n")
    randomSequence(500, 10000, 3000, naiveSampling)
    fmt.Printf("reservoirSampling, sample=500, total=3000\n")
    randomSequence(500, 10000, 3000, reservoirSampling)
    
    fmt.Printf("naiveSampling, sample=1000, total=3000\n")
    randomSequence(1000, 10000, 3000, naiveSampling)
    fmt.Printf("reservoirSampling, sample=1000, total=3000\n")
    randomSequence(1000, 10000, 3000, reservoirSampling)
}

可以看到naiveSampling先不做去重，只统计重复出现采样的数字出现次数，方便计算rr(redundant rate，数据重复率，也就是重复出现的数据)，那么通过两组参数可以看到，在3000个数据里面sample 500个数据，重复率达到7.9%，而3000个数字里面sample 1000个数据，重复率骤增到15%（基本成线性增长），具体结果如下：

naiveSampling, sample=500, total=3000
elapsed=759.6145ms
r|t=394722|5000000, rr=0.078944, sample=3000
m=map[0:1730 1:1697 2:1624 3:1658 4:1664 5:1673 6:1650 7:1672 8:1679 9:1678 10:1668 11:1652 12:1630 13:1661 14:1682 ……]
reservoirSampling, sample=500, total=3000
elapsed=835.8041ms
r|t=0|5000000, rr=0.000000, sample=3000
m=map[0:1585 1:1569 2:1618 3:1682 4:1631 5:1549 6:1646 7:1721 8:1709 9:1610 10:1699 11:1657 12:1645 13:1692 14:1684 ……]
naiveSampling, sample=1000, total=3000
elapsed=1.4001243s
r|t=1494500|10000000, rr=0.149450, sample=3000
m=map[0:3286 1:3222 2:3372 3:3338 4:3302 5:3365 6:3303 7:3403 8:3419 9:3299 10:3315 11:3254 12:3454 13:3362 14:3317 ……]
reservoirSampling, sample=1000, total=3000
elapsed=894.9584ms
r|t=0|10000000, rr=0.000000, sample=3000
m=map[0:3249 1:3393 2:3280 3:3322 4:3276 5:3417 6:3217 7:3345 8:3305 9:3444 10:3299 11:3365 12:3411 13:3276 14:3339 ……]

当然，此时蓄水池算法重复率肯定为0，但是性能会比不去重的naive算法差（去掉map计算去重部分，相对来说，naive性能更好），但是一旦开启了去重，当采样的数据个数达到一定比例，比如总数3000，采样1000个数据时，蓄水池采样算法也不会比naive的更差，有兴趣的可以自己修改下代码，运行得到时间统计。

总结

蓄水池采样算法妙在可以保证每个采样数据的被最终选中的等概率性，而且数学证明上很简洁，通常在数据量位置情况下使用，扩展想，也可以使用在数据量确定情况下，选择k个不重复数据，再扩展些看，如果总数特别大，蓄水池采样算法也可以实现分布式版本，解决单机性能的瓶颈（算力或者存储资源），在此不在赘述，也很简单。过程大致可以为：

1. 假设有K台机器，将大数据集分成K个数据流，每台机器使用单机版蓄水池抽样处理一个数据流，抽样m个数据，并最后记录处理的数据量为N1, N2, ..., NK(假设m<Nk)。N1+N2+...+NK=N。
2. 取[1, N]一个随机数d，若d<N1，则在第一台机器的蓄水池中等概率不放回地（1/m）选取一个数据；若N1<=d<(N1+N2)，则在第二台机器的蓄水池中等概率不放回地选取一个数据；以此类推，重复m次，则最终从N大数据集中选出m个数据。

参考资料

蓄水池抽样算法（Reservoir Sampling）
蓄水池采样算法

节前看了一篇关于Timing Attach的技术博文，还挺有感触的，原文在《这10行比较字符串相等的代码给我整懵了，不信你也来看看》，写得挺好的，自己也想借此整理下，记录下来。这种技术，特别像是灵感，就是你看完之后，会醍醐灌顶的快乐感受。

另类的字符串比较

在 Java 的 Play Framework 里有一段代码用来验证cookie(session)中的数据是否合法（包含签名的验证）的代码，如下所示：

boolean safeEqual(String a, String b) {
   if (a.length() != b.length()) {
       return false;
   }
   int equal = 0;
   for (int i = 0; i < a.length(); i++) {
       equal |= a.charAt(i) ^ b.charAt(i);
   }
   return equal == 0;
}

相信刚看到这段源码的人会感觉挺奇怪的，这个函数的功能是比较两个字符串是否相等，如果要判断两个字符串是否相等，正常人的写法应该是下面这个样子的（golang版本）：

func equals(a, b string) bool {
    if len(a) != len(b) {
        return false
    }

    for i := 0; i < len(a); i++ {
        if a[i] != b[i] {
            return false
        }
    }

    return true
}

我们可以看到，在比较两个字符串是否相等的正常写法是：

先看一下两个字符串长度是否相等，如果不等直接返回 false。
如果长度相等，则依次判断每个字符是否相等，如果不等则返回 false。
如果全部相等，则返回 true。一旦遇到不一样的字符时，直接返回false。
然而，Play Framework里的代码却不是这样的，尤其是上述的第2点，用到了异或，熟悉位操作的你很容易就能看懂，通过异或操作 1^1=0 , 1^0=1, 0^0=0，来比较每一位，如果每一位都相等的话，两个字符串肯定相等，最后存储累计异或值的变量 equal必定为 0（因为相同的字符必然为偶数），否则为 1。

但是，这种异或的方式不是遇到第一个不一样的字符就返回 false 了，而是要做全量比较，这种比较完全没有效率，这是为什么呢？原因是为了安全。

计时攻击（Timing Attack）

计时攻击（Wikipedia）是[旁道攻击]3 的一种，旁通道攻击是指基于从计算机系统的实现中获得的信息的任何攻击 ，而不是基于实现的算法本身的弱点（例如，密码分析和软件错误）。时间信息，功耗，电磁泄漏甚至声音可以提供额外的信息来源，可以加以利用。在很多物理隔绝的环境中（黑盒），往往也能出奇制胜，这类新型攻击的有效性远高于传统的密码分析的数学方法。（注：企图通过社会工程学欺骗或强迫具有合法访问权限的人来破坏密码系统通常不被视为旁道攻击）

计时攻击是最常用的攻击方法。那么，正常的字符串比较是怎么被黑客进行时间攻击的呢？

我们知道，正常的字符串比较，一旦遇到每一个不同的字符就返回失败了，所以，理论上来说，前面只有2个字符相同字符串比较的耗时，要比前面有10个字符相同的比较要短。你会说，这能相差多少呢？可能几微秒吧。但是，我们可以放大这个事。比如，在Web应用时，记录每个请求的返回所需请求时间（一般是毫秒级），如果我们重复50次，我们可以查看平均时间或是p50的时间，以了解哪个字符返回的时间比较长，如果某个我们要尝试的字符串的时间比较长，我们就可以确定地得出这个这字符串的前面一段必然是正确的。（当然，你会说网络请求的燥音太多了，在毫秒级的请求上完全没办判断，这个需要用到统计学来降噪，后面会给出方法）

这个事情，可以用来做HMAC的攻击，所谓HMAC，你可以参看本站的《HTTP API 认证授权术》文章了解更多的细节。简单来说，HMAC，就是客户端向服务端发来一个字符串和其签名字符串（HMAC），然后，服务端的程序用一个私钥来对客户端发来的字符串进行签名得到签名字符串，然后再比较这个签名字符串（所谓签名，也就是使用MD5或SHA这样的哈希算法进行编码，是不可逆的）

写成伪代码大概是这个样子：

bool verify(message, digest) {
    my_digest = HMAC(key, message);
    return my_digest.equals(digest) ;
}

举个例子，如果有一个签名有40个长度，如：f5acdffbf0bb39b2cdf59ccc19625015b33f55fe，攻击者从0000000000000000000000000000000000000000开始穷举，下面是穷举第一个字符（从0到f因为这是HMAC算法的取值范围）的时间统计。

0 0.005450913
1 0.005829198
2 0.004905407
3 0.005286876
4 0.005597611
5 0.004814430
6 0.004969118
7 0.005335884
8 0.004433182
9 0.004440246
a 0.004860263
b 0.004561121
c 0.004463188
d 0.004406799
e 0.004978907
f 0.004887240

可以看到，第一次测试通过的计时结果（以秒为单位），而值“ f”与样品的其余部分之间没有较大的变化量，所有结果看起来都非常接近。换句话说，有很多噪声掩盖了信号。因此，有必要进行多个采样（对测试进行缩放）并使用统计工具从噪声中滤除信号。为了将信号与噪声分开，我们必须按任意常数对测试进行缩放。通过实验，作者发现500是一个很好的数字。换句话说：运行测试500次，并记录500个试验中每个试验的结果。然后，通过人的肉眼观察可以可能看到 f 的调用明显比别的要长，但是这种方法很难自动化。

所以，作者给了另一个统计算法，这个算法向服务器分别从 0 到 f 发出16个请求，并记录每个请求的响应时间，并将它们排序为1-16，其中1是最长（最慢）的请求，而16是最短（最快的请求），分别记录 0 – f 的名次，然后重复上述的过程 500 次。如下所示（仅显示25个样本，字符“ 0”首先被排名7、1、3，然后再次排名3……）：

{
"0"=>[7, 1, 3, 3, 15, 5, 4, 9, 15, 10, 13, 2, 14, 9, 4, 14, 7, 9, 15, 2, 14, 9, 14, 6, 11...],
"1"=>[13, 4, 7, 11, 0, 4, 0, 2, 14, 11, 6, 7, 2, 2, 14, 11, 8, 10, 5, 13, 11, 7, 4, 9, 3...],
"2"=>[14, 5, 15, 5, 1, 0, 3, 1, 9, 12, 4, 4, 1, 1, 8, 6, 9, 4, 9, 5, 8, 3, 12, 8, 5...],
"3"=>[15, 2, 9, 7, 2, 1, 14, 11, 7, 8, 8, 1, 4, 7, 12, 15, 13, 0, 4, 1, 7, 0, 3, 0, 0...],
"4"=>[12, 10, 14, 15, 8, 9, 10, 12, 10, 4, 1, 13, 15, 15, 3, 1, 6, 8, 2, 6, 15, 4, 0, 3, 2...],
"5"=>[5, 13, 13, 12, 7, 8, 13, 14, 3, 13, 2, 12, 7, 14, 2, 10, 12, 5, 8, 0, 4, 10, 5, 10, 12...]
"6"=>[0, 15, 11, 13, 5, 15, 8, 8, 4, 7, 12, 9, 10, 11, 11, 7, 0, 6, 0, 9, 2, 6, 15, 13, 14...]
"7"=>[1, 9, 0, 10, 6, 6, 2, 4, 12, 9, 5, 10, 5, 10, 7, 2, 4, 14, 6, 7, 13, 11, 6, 12, 4...],
"8"=>[4, 0, 2, 1, 9, 11, 12, 13, 11, 14, 0, 15, 9, 0, 0, 13, 11, 13, 1, 8, 6, 5, 11, 15, 7...],
"9"=>[11, 11, 10, 4, 13, 7, 6, 3, 2, 2, 14, 5, 3, 3, 15, 9, 14, 7, 10, 3, 0, 14, 1, 5, 15...],
"a"=>[8, 3, 6, 14, 10, 2, 7, 5, 1, 3, 3, 0, 0, 6, 10, 12, 15, 12, 12, 15, 9, 13, 13, 11, 9...],
"b"=>[9, 12, 5, 8, 3, 3, 5, 15, 0, 6, 11, 11, 12, 8, 1, 3, 1, 11, 11, 14, 5, 1, 2, 1, 6...],
"c"=>[6, 7, 8, 2, 12, 10, 9, 10, 6, 1, 10, 8, 6, 4, 6, 4, 3, 2, 7, 11, 1, 8, 7, 2, 13...],
"d"=>[2, 14, 4, 0, 14, 12, 11, 0, 8, 0, 15, 3, 8, 12, 5, 0, 10, 1, 3, 4, 12, 12, 8, 14, 8...],
"e"=>[10, 8, 12, 6, 11, 13, 1, 6, 13, 5, 7, 14, 11, 5, 9, 5, 2, 15, 14, 10, 10, 2, 10, 4, 1...],
"f"=>[3, 6, 1, 9, 4, 14, 15, 7, 5, 15, 9, 6, 13, 13, 13, 8, 5, 3, 13, 12, 3, 15, 9, 7, 10...]
}

然后将每个字符的500个排名进行平均，得出以下示例输出：

"f", 5.302
"0", 7.17
"6", 7.396
"3", 7.472
"5", 7.562
"a", 7.602
"2", 7.608
"8", 7.626
"9", 7.688
"b", 7.698
"1", 7.704
"e", 7.812
"4", 7.82
"d", 7.826
"7", 7.854
"c", 7.86

于是，f 就这样脱颖而出了。然后，再对剩余的39个字符重复此算法。

这是一种统计技术，可让我们从噪声中滤出真实的信号。因此，总共需要调用：16 500 40 = 320,000个请求，而蛮力穷举需要花费16 ^ 40个请求。

另外，学术界的这篇论文就宣称用这种计时攻击的方法破解了 OpenSSL 0.9.7 的RSA加密算法了。这篇 Remote Timing Attacks are Practical （PDF）论文中指出（我大致翻译下摘要，感兴趣的同学可以通过链接去看原文）：

计时攻击往往用于攻击一些性能较弱的计算设备，例如一些智能卡。我们通过实验发现，也能用于攻击普通的软件系统。本文通过实验证明，通过这种计时攻击方式能够攻破一个基于 OpenSSL 的 web 服务器的私钥。结果证明计时攻击用于进行网络攻击在实践中可行的，因此各大安全系统需要抵御这种风险。

导言

什么是主定理，引用维基百科的介绍，在算法分析中，主定理（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。所以，在算法复杂度分析时，我们经常需要使用主定理做复杂度的推导，尤其是各种类型的分治算法，比如二分搜索、归并排序、二叉树的遍历等算法。

理论

算法存在递推关系式

证明

总结

以上的证明手写输出，在电脑上面打公式太麻烦，另外证明过程采用的比较简单直接的方式，没有使用特别严格的数学证明方法，便于理解，简单来说，如果a<b^d，那么T(n)主要看O(n^d)这项，如果a==b^d，那么T(n)需要看展开的每一项，如果a>b^d，那么最主要的是看展开后的最后一层子问题，后面有时间，会补充一篇根据主定理推导算法复杂度的文章。