我正在尝试解决一个问题，其中我想将向量的元素与相同向量的所有元素相乘（也与self相乘）。
我有一个可行的解决方案，如下所示：
for(int i=0;i<v.size();i++)
{
for(int j=0;j<v.size();j++)
{
r.insert(v[i]*v[j]);
}
}
这里v是最初存储我的元素r的向量，也是我存储产品的向量。
我面临的问题：
这是一个O（N ^ 2）算法，我想在O（N）时间内实现。有什么办法可以做到这一点？谢谢。
编辑1：
实际上，我想在通过将向量元素与其他元素相乘而获得的数字列表中找到第n个最大数字。我的方法是：
我想提高N ^ 2的时间复杂度。
您可以做的是避免两次计算相同的值。确实，通过您的解决方案，所有对将相乘两次。如果您在矩阵中显示结果值，则将最好地看到这一点：
input: [a, b, c]
output:
aa ba ca
ab bb cb
ac bc cc
您可以看到对角线两侧的对称性。这意味着在计算第n列时，您只需要计算size of input - n值，因为其他值n已经存在于前面的列中，您可以在其中检索它们。
请注意，尽管如此，这不会影响算法的复杂性。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句