算法导论1.2 Exercises 答案

1.2-1

布隆过滤器：用于检索一个元素是否在一个集合中。

具体场景：现在有一个非常大的黑名单URL集合。但是这些URL的长度都是固定的。现在需要过滤网站，判断网页的URL是否是否在黑名单上。允许有微小的判断失误率。并且要求使用的空间有限。

1.2-2

不难发现，这题是求\(n\)使得\(8n^2>64n\lg n\)。得到满足的\(n\)满足\(1< n< 44\)。

1.2-3

不难发现，这题是求最小的\(n\)使得\(100n^2<2^n\)，得到满足的\(n\)值为\(15\)。