找到最大平方和的算法

Question

假设我给了一堆数字对，除了计算所有平方和并将其与当前最大值进行比较之外，还有一个很好的算法来找到具有最大平方和的对吗？

例如输入：

[3, 3]
[0, 3]
[4, 0]
[2, 4]

输出：[2, 4]（平方和：20）

Answer 1

要使用二进制搜索，您需要对列表进行排序。这引发了两个问题（上面提到或暗示过）：

• 你没有一个井然有序的集合
• 最佳排序是O（n log n）

两个正方形的总和很简单：数字的两次数据访问，两次乘法和一次加法。在线性CPU上，这可以实现3个廉价（即单周期）操作。在现代AI处理器上，这是一个单周期点积。

简而言之，不仅线性，强力逼近O（n），它还是快速O（n）。拿钱跑。