我们知道,求得一场考试的题目难度,是一个 NP 问题(其证书为一场考试的全体成绩)。但我们可以用以下方法来近似求解一场考试的题目难度:
在考试结束后,在课程群里发以下图片,并统计复读该图片的同学数量占总人数的比例。这是对考试题目难度的一个 epsilon-delta 近似。
我们可以用 Locality-Sensitive Hashing 的方法来近似得到复读图片的人数。即,使用 Reservoir Sampling 得到一个全体同学的大小为 k 的无放回采样,并定义哈希函数 H(x) = 同学 x 是否复读了该图片。这是一个 (d1, d2, p1, p2)-sensitive 的哈希函数,在该算法之上应用多个哈希函数 AND 和 OR 的组合可以增大 p1 并减小 p2。
如果有一名同学复读了多次该图片,则说明这名同学认为这场考试的题目难度极大,令所有复读次数为 ||f1||,我们可以使用一个适当大小的 Count-Min Sketch 来统计有多少名同学复读的图片数量占总复读数量的 phi 倍以上,并保证在 1-delta 的概率下统计正确。
