关于 gp_hash_table 和 cc_hash_table
  • 板块学术版
  • 楼主Z1qqurat
  • 当前回复18
  • 已保存回复18
  • 发布时间2024/1/25 11:33
  • 上次更新2024/1/25 14:15:20
查看原帖
关于 gp_hash_table 和 cc_hash_table
483928
Z1qqurat楼主2024/1/25 11:33

是由 这个题 引起的疑问。

  • 好像各种资料上都说 gp_hash_table 跑得比 cc_hash_table 快一些,尤其是在随机数据下,但是这题中我使用了哈希表维护当前有值的位置,我认为都是 O(1)\mathcal{O}(1) 操作的,但是实际上两者效率差别极大,使用 gp_hash_table 完全跑不过,但是我改成 使用 cc_hash_table 就能跑过去,(不过这种做法只能在 loj 神机上通过,洛谷上无论写哪个都会 T,但是仍然是 cc_hash_table 可以跑过更多测试点)。这是为什么呢?是因为 gp_hash_table 被卡了吗?

  • 遍历 cc_hash_table 的复杂度究竟是多少呢?比如我的写法里面只保留了值不为 00 的位置,这些位置至多 n\sqrt n 个,那我遍历的复杂度是 O(size)\mathcal{O}(size) 的还是要多一个 log⁡\log 呢?

还有这个题是不是过于卡常了。。。

2024/1/25 11:33
加载中...