c - 用于快速查询的整数 vector 散列

Question

我用 3x2 vector 表示单项式。例如，

x y z   : ( (variable id, exponent of variable) ) 

        : ( (1,1) , (2, 1) , (3,1) )

x^2 z^2 : ( (1,2) , (3,2) , (null, null) )

不同变量的总数是一百万，但一个单项式最多包含三个不同变量。

我想做这样的查询

1. x 是否在单项式 y^2 z^2 中？
2. 在 y^2 z^2 中 y 的幂是否大于 3？

是否有一个哈希函数可以在 O(1) 中回答这些问题？
或者我应该只遍历 3x2 vector 吗？

我问是因为我维护了一个包含 500 万个这样的单项式的哈希表。因此，默认情况下，我必须使用散列结构进行搜索。也许有一种哈希方案也可以回答上述两个问题。

相关问题:best codebook for manipulation of monomials

Answer 1

我认为您必须遍历 3x2 vector 。

有人可能会争辩说循环 vector 是一种 O(1) 操作。为什么？因为 vector 中的条目数恰好是 3，这是一个很小的常量。换句话说，循环计数与大数无关:

• n 是变量的数量，
• m 这是单项式的数量。

m 和 n 有多大(或多小)无关紧要，循环遍历 vector 总是花费相同的时间，所以它在技术上是一个 O (1)操作。