3.1.15 #

解答 #

假设先全部 Put()，再进行查找操作。

即分别进行 $1$, $10 ^ 3$, $10 ^ 6$ 次插入

$N = 1$ 时，可以直接得出比例 $0.1 %$。

$N = 10 ^ 3$ 时，

插入耗时 $= 1 + 2 + … + 10 ^ 3 = 500500$，

查询耗时 $= 10 ^ 6 * \lg(10 ^ 3) = 9965784$，

比例为 $4.782 %$。

$N = 10 ^ 6$ 时

插入耗时 $= 1 + 2 + … + 10 ^ 6 = 500000500000$，

查询耗时 $= 10 ^ 9 * \lg(10 ^ 6) = 19931568569$，

比例为 $ 96.17 % ​$。