我有一个长度为N=10^5的数组。对于每个索引1<i<n
我必须计算A[j]-A[i] and (j-i) is prime and j>i 之间的差异
这是我的代码：
for(int i=1;i<=n;i++){
for(int j=0;j<prime.size();j++){
int x = prime.get(j);
if(x+i>n) break;
ans+= A[x+i]-A[i];
}
}
我应该如何使这项工作更快？我认为时间复杂度是O（N*prime.size）
首先，我将重新表述您的问题，使其说明我认为您想要实现的目标。你可能在寻找形式A[j]-A[i]的差的和，其中(j-i)是"正"素数，1<=i<j<=N。记住这句话。。。
我们计算A[k]被加到和上的次数（由p表示）和从和上减去A[k]的次数（以m表示）。好吧，m等于区间[1,N-k]中的素数，而p等于区间[1,k-1]中的素数。如果你不相信我的话，可以一步一步地模拟你的代码。然后你可以做：
S = 0
for k = 1 to N do
S = S + (p(k) - m(k)) * A[k]
endfor
现在，我们需要找到一种方法来有效地确定区间[1,N]中每个k的p和m。我看到你已经构建了一个素数的有序列表。那么，为了回答形式为"区间[1,t]中有多少素数？"您可以在该列表上执行CCD_ 19的二进制搜索。这将使复杂性降低到O(N*log(prime.size))。
作为替代方案，您可以预先计算形式为"在区间[1,t]中有多少素数？"的查询的答案。您需要一个大小为N的额外数组nrPrimesLessThan来保存结果，这样做可以计算其值：
count = 0
for i = 1 to N do
if i < prime.get(count) then
nrPrimesLessThan[i] = count
else
count = count + 1
nrPrimesLessThan[i] = count
endif
endfor
预计算部分需要O(N)步，但现在一个查询需要O(1)步，因此计算和需要O(N)步。总体而言，N中的线性时间。
根据您的代码示例判断，您希望对数组中所有值对的差求和，其中索引的差为素数。你已经有一组素数了。
下图显示了元素是如何相减和相加的：
0 1 2 3 4 5 6 7 8 9
- + + + + 0
- + + + + 1
- + + + + 2
- + + + 3
- + + + 4
- + + 5
- + + 6
- + 7
- 8
- 9
+意味着一个元素被添加到总和中。-表示从和中减去元素。这不是一个单一的减法；左边的每一个加法都会进行减法运算，因此A[0]被减去4次。它从未被添加。
另一方面，A[9]从不被减去，而是被加了四次。通常，每一个元素减去的次数与行中的加号的次数一样多，相加的次数与列中的加号数量一样多。这里有一个对称性：
add[i] = sub[N - i - 1]
对于基于零的索引。add[i]的值是多少？它是小于或等于i的素数。
下面是一个代码示例，其中add阵列被称为m:
int psum2(const int A[], int n)
{
int sum = 0;
int m[n];
int j = 0;
int k = 0;
for (int i = 0; i < n; i++) {
if (i == prime[j]) {
k++;
j++;
}
m[i] = k;
}
for (int i = 0; i < n; i++) {
sum += (m[i] - m[n - i - 1]) * A[i];
}
return sum;
}
数组m总是相同的，如果需要更频繁地执行求和，则可以预先计算。算法是O（n）。
这个问题也与本质上的素数无关。上面的方法适用于所有的条件差和，其中指数的差必须在某一组数字中竞争。