algorithm - 如何在 O(m+n) 中获取两个稀疏向量的点积，其中 m 和 n 是两个向量中的元素数

Question

我有两个稀疏向量 X 和 Y，想得到 O(m+n) 的点积，其中 m 和 n 是 X 和 Y 中非零元素的数量。我能想到的唯一方法是选择向量 X 中的每个元素并遍历向量 Y 以查找是否存在具有相同索引的元素。但这需要 O(m * n)。我将矢量实现为链表，每个节点都有一个元素。

Answer 1

如果您的向量存储为元组的链接列表，每个元组包含索引和非零元素的值并按索引排序，您就可以这样做。

您通过从较低索引处的向量中选择下一个元素来遍历两个向量。如果索引相同，则将元素相乘并存储结果。

重复直到一个列表到达末尾。

由于每个列表中的每个非零元素都有一个步骤，因此根据需要复杂度为 O(m+n)。

脚注:数据结构不必是链表，但必须提供 O(1) 方法来访问下一个非 0 元素及其索引。