相同的时间复杂，但运行时间变化很大

Question

对于问题：给定一个偶数(大于2)，返回两个素数，其总和将等于给定数。

以下算法的时间复杂度分别为O(A^2.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;    
}

Answer 1

时间复杂度不是关于算法运行的速度，而是关于随着问题变大，它的速度如何缩放。在每个元素上花费 1 秒的算法与在每个元素上花费 1 微秒的算法具有相同的时间复杂度：O(n)。在这两种情况下，如果您有 10 倍的元素，则算法的运行时间将是原来的 10 倍。

Answer 2

您考虑的复杂性不会为您提供有关算法性能的即时信息，而是提供有关渐近行为的信息，通常用于最坏的情况。

---

最坏情况与平均情况

看看A = 73939138的答案就知道了：

73939138 = 5 + 73939133

所以基本上，你的第一个算法对check进行~10次调用，而第二个算法正在经历巨大的循环来填充数组primes。

第一种算法的平均复杂度可能远低于O(A^2.5)，而第二种算法的平均情况复杂度接近或等于O(A log(log(A))。

注意：接下来关于平均情况复杂性的内容只是猜测，不要将它们视为合理的结果。

第二种算法：

在这个算法中，无论A是什么，你都必须使用埃拉托色尼的筛子填充数组primes，这是O(A log(log(A)))。由于这是算法中最耗时的部分，因此该算法的平均情况复杂度可能接近其最坏情况的复杂性，因此O(A log(log(A))).

第一种算法：

这里更复杂...基本上，这取决于算法的结果。根据维基百科关于哥德巴赫猜想的页面，将A写为两个素数之和的平均方式数量是A / (2 * log(A) ^ 2)。

由于素数不能以两种不同的方式做出贡献，这意味着平均有2 * A / (2 * log(A) ^ 2) = A / (log(A) ^ 2)素数对其中一种方式做出贡献。

如果我们**假设*¹这些素数是均匀分布的，那么较小的素数应该接近A / (A / log(A) ^ 2) = log(A)^2。

因此，您只需要检查最多大约log(A)^2的数字。

_{¹我完全不知道这是否属实，我只是在猜测......}

---

渐 近

查看@PeterBecker的答案和评论。

当你说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"实体" — 这可能是通过std::vector<bool>的专业化优化的，但您仍然需要 ~9MB，它不适合 L1 缓存，也许是 L2，并且每次访问都需要一些按位操作。
  • arr应包含 ~4000000 个int(请参阅此处)，并且由于您使用的是push_back，因此需要多个分配。