对于这个问题:给定一个偶数(大于 2 )，返回两个素数，它们的总和将等于给定的数字。
以下算法的时间复杂度分别为 O(A2.5) 和 O(Alog(log(A))。仍然对于 A(整数)的值大到 73939138 的第二个算法真的很慢。我已经尝试了很多输入，第一个更快。你能解释一下为什么吗？
int ul=A/2;
vector <int> answer;
for (int i=1; i<=ul; i++)
{
if (check(i)==1 && check(A-i)==1 ) //check(i) checks primality of i in O(i^1.5)
{
int myint[2] ={ i,A-i };
answer.assign( myint, myint+2);
return answer;
}
}
vector<bool> primes(A+1,true);
int i,j;
//Sieve of Eratosthenes O(Alog(log(A)))
for(i=2;i*i<A+1;i++)
{
if(primes[i])
{
for(j=2;i*j<A+1;j++)
primes[i*j]=0;
}
}
vector<int> arr,answer;
//arr is vector containing all primes from 2 to A; O(A)
for(i=2;i<A+1;i++)
{
if(primes[i])
arr.push_back(i);
}
i=0;j=arr.size()-1;
//Algorithm to find 2 numbers summing up to a value
while(i<=j)
{
if(arr[i]+arr[j]>A)
j--;
else if(arr[i]+arr[j]<A)
i++;
else
{
answer.push_back(arr[i]);
answer.push_back(arr[j]);
return answer;
}
}
编辑:check(n) 定义如下:
int check(int n)
{
int ul=sqrt(n);
if(n<2)
return 0;
for(int i=2; i<=ul; i++)
{
if(n%i==0)
return 0;
}
return 1;
}
最佳答案
您考虑的复杂性不会为您提供有关算法性能的即时信息，而是有关 渐近 行为的信息，通常用于 最坏情况 场景。
最坏情况与平均情况
看看 A = 73939138 的答案:
73939138 = 5 + 73939133
所以基本上，你的第一个算法对
check 进行了大约 10 次调用，而第二个算法则通过巨大的循环来填充数组 primes ..第一种算法的 平均情况 复杂度可能远低于
O(A^2.5) ，而第二种算法的平均情况复杂度接近或等于 O(A log(log(A)) 。注意: 以下关于平均情况复杂度的内容只是猜测，不要将它们视为可靠的结果。
第二个算法:
在这个算法中，无论
A 是什么，你都必须使用 Eratosthenes 的筛子来填充数组 primes ，即 O(A log(log(A))) 。由于这是算法中最耗时的部分，因此该算法的平均复杂度可能接近其最坏情况的复杂度，因此 O(A log(log(A))) 。第一个算法:
这里比较复杂……基本上看算法的结果。根据 Wikipedia's page on Goldbach's conjecture ，将
A 写成两个素数之和的平均方式数是 A / (2 * log(A) ^ 2) 。由于素数不能对两种不同的方式做出贡献，这意味着平均有
2 * A / (2 * log(A) ^ 2) = A / (log(A) ^ 2) 素数有助于其中一种方式。如果我们**假设*1这些素数是均匀分布的，那么较小的应该接近
A / (A / log(A) ^ 2) = log(A)^2 。所以你只需要检查大约
log(A)^2 的数字。1 我有 完全不知道 如果这是真的，我只是在猜测......
渐近行为
检查 @PeterBecker's answer and comments 。
当你说
O(A log(log(A))) 复杂性时，你隐藏了很多东西——f(A) = C * (A log(log(A))) + g(A) 是 g(A) 的任何函数 O(A log(log(A))) 也是 O(A log(log(A))) 。例如:
f(A) = c1 * A * log(log(A)) + c2 * A + c3 * log(A)
...是
O(A log(log(A))) 。系数
c1 、 c2 、 c3 决定了算法实现的真实行为，不幸的是，这些系数通常很难找到(或很复杂)。例如，快速浏览一下您的实现会显示以下内容:
primes 和 arr——如果 A = 73939138 :primes 包含 73939139 "entity"— 这可能是通过 std::vector<bool> 的特化优化的，但你仍然需要 ~9MB，它不适合 L1 缓存，可能是 L2，并且每次访问都需要一些位操作. arr 应包含 ~4000000 int(请参阅 here )，并且您需要多次分配，因为您使用的是 push_back 。 关于c++ - 相同的时间复杂度但运行时间差异很大，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48096682/