Alt*_*aïr 3 algorithm big-o linear-algebra
我有两个稀疏的向量X和Y,并希望得到O(m + n)中的点积,其中m和n是X和Y中非零元素的数量.我能想到的唯一方法是选择每个元素在向量X中并遍历向量Y以查找是否存在具有相同索引的元素.但这需要O(m*n).我将矢量实现为链表,每个节点都有一个元素.
如果您的向量存储为元组的链表,并且每个元组包含索引和非零元素的值并按索引排序,则可以执行此操作.
通过从矢量中选择下一个元素来迭代两个向量,您可以在较低的索引处.如果索引相同,则将元素相乘并存储结果.
重复,直到一个列表到达结尾.
由于每个列表中每个非零元素都有一步,因此复杂度为O(m + n).
脚注:数据结构不必是链表,但必须提供O(1)方式来访问下一个非0元素及其索引.
| 归档时间： |
|
| 查看次数： |
5408 次 |
| 最近记录： |