怎么优化计算绝对值(街区距离)的和的时间复杂度

如何优化计算绝对值(街区距离)的和的时间复杂度

有比直接计算
|a_1 - b_1| + |a_2 - b_2|
这个复杂度更低的算法吗？
[解决办法]
即使有也会增加其复杂度，你总得拼凑64位整数。

直接计算已经是最小复杂度了。

引用:

假设a,b的每个分量是8位的字节数据
可以将8个a分量和b分量，凑成64位整形来计算
有特别的指令取出64位整数的每个字节，并相加吗？

[解决办法]
你需要的是硬件指令而不是算法
[解决办法]
如果这个是核心重要的话——可以专门做个小集成块来实现。
[解决办法]
算一个用不上什么算法，挨个算就好了。从一堆中找最近，则可以试试KDTree。
[解决办法]
1范数可以用SSE指令优化, 2范数其实也可以, 不过要考虑溢出, 一次做的没1范数那么多.

查看更多 下一篇