时间复杂度相同但运行时间差异很大

Question

对于问题：给定一个偶数（大于 2），return 两个质数之和等于给定数。

以下算法的时间复杂度分别为 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

时间复杂度不是关于算法快的运行s，而是关于它的速度scales 随着问题变大。在每个元素上花费 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 是什么，您都必须使用 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) 个素数对其中一种方式有贡献。

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

因此您只需检查大约 log(A)^2.

的数字

_{¹我完全不知道如果这是真的，我只是猜测...}

渐近行为

检查。

当您说 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，这不适合一级缓存，也许是二级缓存，每次访问都需要一些位运算。
- arr 应该包含 ~4000000 int（参见 here），并且您需要多次分配，因为您正在使用 push_back.

时间复杂度相同但运行时间差异很大

Same time complexty but highly varying runtimes

c++

algorithm

primes

最坏情况与平均情况

渐近行为