3.1.15

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

假设先全部 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 \% ​$。

上一题 下一题