问题：对一个包含15亿个QQ号的文件进行去重

算法1：数组解法

将QQ号读入内存，组成一个数组。然后遍历这个数组与其他位置比对，如果遇到重复的号码，则表示存在重复。

该算法时间复杂度n^2, 15亿个号码循环次数为(15亿)^2。

所有QQ号码存入内存中，每个QQ号码占用一个整形，一般为32个bit, 空间需要15亿*32个bit约等于5.59G

算法2: HashMap解法

内存中保存一个HashMap, 遍历所有号码，如果HashMap中存在该号码，则表示存在重复。如果不存在该号码，将号码存入HashMap中。

由于HashMap的存和取在不存在Hash冲突的情况下为O(1)复杂度，所以该算法时间复杂度为O(n)。虽然算法2在时间复杂度上大大优于算法1，但是由于HashMap数据结构占用空间较大，如果15亿个号码都不重复，需存入HashMap中，仅考虑HashMap内数组存储的15亿个Entry的Key需占用空间同样为57220G，再加上存储的15亿个value，空间占用都肯定大于5.59G。

算法3：BitMap解法

我们先把问题简化，15亿个号码简化为10个10以内的号码去重，假设号码分别是

1, 2, 3, 4, 1, 3, 9, 8, 7, 6

我们使用BitMap来标记每个数字是否存在，

BitMap初始化使用一个10位的Bit数组，各位都初始化为0，    则

BitMap为  0000000000

数字1, 取BitMap第1位的值，为0, 表示1不存在重复的值，将BitMap第1位标记为1，则BitMap为 0000000001

数字2, 取BitMap第2位的值，为0，表示2不存在重复的值，将BitMap第2位标记为1，则BitMap为 0000000011

数字3，取BitMap第3位的值，为0，表示3不存在重复的值，将BitMap第3位标记为1，则BitMap为 0000000111

数字4，取BitMap第4位的值，为0，表示4不存在重复的值，将BitMap第4位标记为1，则BitMap为 0000001111

数字1，取BitMap第1位的值，为1，表示1存在重复的值，不标记BitMap，则

BitMap为 0000001111

数字3，取BitMap第3位的值，为1，表示2存在重复的值，  不标记BitMap，则

BitMap为 0000001111

数字9，取BitMap第9位的值，为0，表示9不存在重复的值， 将BitMap第9位标记为1，则BitMap为 0100001111

数字8，取BitMap第8位的值，为0，表示8不存在重复的值， 将BitMap第8位标记为1，则BitMap为 0110001111

数字7，取BitMap第8位的值，为0，表示7不存在重复的值， 将BitMap第7位标记为1，则BitMap为 0111001111

数字6，取BitMap第8位的值，为0，表示6不存在重复的值， 将BitMap第6位标记为1，则BitMap为 0111101111

最终BitMap为0111101111

遍历BitMap的各位，如果该位为1，则表明存在数值为该位位数的数值，这样可以得到去重后的所有数值

为 9,8,7,6,4,3,2,1

该方法推广到15亿个号码去重，则使用的BitMap为15亿位，算法时间复杂度同样为O(n), 占用空间约等于15亿个bit约等于174.62M

可以看出，BitMap在大数据量，重复度不高的数值去重场景的空间占用方面有比较大的优势。

如果数值的重复度比较高,例如存在99.99%的重复，BitMap依然要占用15亿*100%个bit的空间，

而HashMap仅存储不重复的数值，则HashMap解法占用空间将变为原空间的0.01%

这种情况下BitMap与HashMap的空间占用优劣势就需要重新进行衡量。

如果暴力法求2的平方根，应该是二分查找，不断的用中点的平方与2进行对比，然后根据对比结果改变查找结果的范围。

这种方法如果要求精确度比较高的时候，查找的次数将非常可观。该算法暂且不在本文讨论。

本文要讨论的是一种可以快速求解函数零点的算法-牛顿迭代，可以用在求2的平方根上。

此牛顿即科学之父，艾萨克·牛顿。

求2的平方根，其实就是求 f(x) = x² – 2函数，当f(x)=0时x的解。

如何找到这个x的值，在牛顿迭代算法中的方法是随机选择曲线f(x)上的一个点。

假设第一个选取的是(x₀, y₀) = (4, 14)。

如图1可以看出该点的切线与x轴的交点(x₁, 0)是一个更加接近(x, 0)的值。

那么如何求x₁的值，我们需要求切线的函数。

切线是一条直线，已知该切线经过(x₀, y₀)，(x₁, 0)两点，且切线的斜率为2x₀(斜率的推导先搁置，文末会详细推导)。

所以，可得

0-y₀ = (x₁ – x₀)*2x₀

x₁ = x₀ – y₀/(2x₀) 

x₁= x₀ – (x₀² – 2)/2x₀

因为x₀=4, 所以x₁= 4 – 14/(2*4) = 2.25

如图2

在(x₁, 0)作一条垂直x轴的直线与f(x)曲线的交点为(x₁, y₁)，

则(x₁, y₁)点的切线与x轴的交点为(x₂, 0)。

(x₂, y₂)点的切线与x轴的交点为(x₃, 0)。

(x₃, y₃)点的切线与x轴的交点为(x₄, 0)。

……

所以整个迭代过程如下：

x₀=4.0000000000

x₁=2.2500000000

x₂=1.5694444444

x₃=1.4218903638

x₄=1.4142342859

x₅=1.4142135625

x₆=1.4142135624

……

随着不断迭代，切线交点不断向x接近，最终可以得到一个x的近似值，当达到一定的精确度之后，迭代停止。

此迭代思路亦可应用于其他函数零点的求解中，只需改变对应的曲线和切线的函数即可。

Java代码实现，递归实现

public class Newton { public static void main(String[] args) { double x = newton(2); } private static double newton(double x) { if (Math.abs(x * x - 2) > 0.0000000001) { // 精确度达到小数点后10位停止迭代 return newton(x - (x * x - 2) / (2 * x)); } else { return x; } } }

附录

f(x) = x² – 2 函数曲线的切线斜率的推导

需要使用微积分的思维

我们知道曲线上两点(x₀, y₀)(x₁, y₁)连线的斜率的求解方法为

(y₀-y₁)/(x₀ – x₁)

y₀=x₀² – 2

y₁=x₁² – 2

代入斜率计算公式 = ((x₀² – 2) – (x₁² – 2))/(x₀ – x₁) 

=(x₀² – x₁²)/(x₀ – x1) 

=(x₀ – x₁)*(x₀ + x₁)/(x₀ – x₁)

 =x₀ + x₁

当(x₀, y₀)(x₁, y₁)无限接近(x, y)时的直线的斜率即为该点的切线斜率

lim(x₀ + x₁) = 2x

可求得点(x, y)的切线斜率 = 2x