克服 n^2 运行时程序

Question

有没有办法克服 C++11 中的嵌套循环递归？我的程序运行速度慢。或者更确切地说，是否有更有效的方法来解决以下公式 z=|a-b|*|x-y|，其中 a、b、x 和 y 是 10000 整数数组中的元素？

代码如下：

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

ifstream in("int.in");

int main()
{
    long long n, n1, z, x, y, in2=0;
    in>>n
    long long l[n], p[n];
    for(x=0;x!=n;x++)
        in>>l[x]>>p[x];
    for(x=0;x!=n;x++)
    {
        for(y=x+1;y<n;y++)
        {
            ineq+=(abs(l[x]-l[y])*abs(p[x]-p[y]))); //executes slow
            /*n1=l[x]-l[y]; //Alternative algorithm
            if(n1<0)
                n1*=-1;
            z=p[x]-p[y];
            if(z<0)
                z*=-1;
            in2+=n1*z;*/
        }
    }
    cout<<in2<<"\n";
}

我尝试将数据类型更改为 short int、long、long long 和 unsigned，但它要么转储垃圾值，要么执行``Segmentation Core Fault `错误。

对于绝对值公式，我最初尝试使用硬编码方法（已注释掉），但它似乎输出垃圾值。我也尝试用 abs() 函数 ineq+=abs(l[x]-l[y])*abs(p[x]-p[y])); 优化 abs 解决方案，但它似乎执行得更慢。我不知道我可以实现任何其他优化，所以请推荐一些。

Linux-友好的解决方案首选。谢谢。

旁注：a,b,x,y的值都在1<=a,b,x,y<=10000.

范围内

旁注：此程序从文件 "int.in" 读取，取第一个整数（项目数）并成对读取每个新行（l[x] 和 p[x] 是成对的） .

旁注：我也试过只使用多维数组，但我在某处读到一维数组在 CPU 缓存中，而多维数组分散在内存中并且速度较慢。

Answer 1

这个问题可以换一种方式来画：你在等式z=c*d（当然c is |a-b| 和 d is |x-y|).

所以首先订购你的阵列。然后寻找 z=c*d 的解决方案，然后找到使 c == a - b 为真的 a 和 b 以及使 d == x - y 为真的 x 和 y。

完成后，您将获得使方程式成立的所有值，因为 abs(a-b) 与 abs(b-a) 相同

克服 n^2 运行时程序

Overcoming an n^2 runtime program

c++

c++11

types

absolute-value