算法导论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$。