c# - c# 中的 Baby-Step Giant Step 算法。哈希表内存不足

Question

我正在尝试使用哈希表来解决离散算法问题。我正在使用 Shanks baby step giant step 算法。我的哈希表包含大约 11,000,000 个键和值。我不断收到内存不足异常。有没有什么办法解决这一问题？还是要使用不同的数据结构？我正在使用带有 .NET 4.0 Framework 的 Visual C# Express 2010

Answer 1

我觉得这有点作弊，但是Wikipedia给出解决方案

“该算法需要 O(m) 内存。在算法的第一步中选择较小的 m 可以使用更少的内存。这样做会增加运行时间，然后是 O(n/m)。或者，可以使用 Pollard 的 rho 算法来求对数，它的运行时间与小步巨步算法大致相同，但内存需求很小。”