时间复杂度不同但运行时反差大：两素数求和算法性能问询

这是个很有意思的问题——理论时间复杂度看起来碾压的算法，实际跑大数值时反而拉胯，核心原因在于理论复杂度是最坏情况的上限，而实际运行时的真实开销要看具体场景的特性。咱们来拆解一下两种算法的实际表现：

1. 第一种算法的「提前终止」特性是关键 #

第一种算法的思路是从i=1开始遍历到A/2，一旦找到第一个满足i和A-i都是素数的组合就直接返回。而根据哥德巴赫猜想（对于大于2的偶数，这个猜想已经被验证到极大的数值范围，包括你测试的73939138），这样的组合不仅存在，而且通常出现在很小的i值上。

比如拿73939138来说，你可能只需要试到i=3、i=7或者i=11就能找到符合条件的素数对，根本不会遍历到A/2。这时候第一种算法的实际操作数，只是几次素性检测的开销——哪怕每次素性检测是O(sqrt(n))，对于A-i这种大数值，sqrt(7e7)也才约8600次循环，几次下来总操作数也就几万次，和理论最坏情况的O(A^2.5)差了好几个数量级。

2. 埃氏筛的「固定开销」太大 #

第二种算法的核心是先做一次埃氏筛，生成2到A之间的所有素数。虽然理论复杂度是O(A log log A)，但对于A=7e7这个量级：

• 筛法需要遍历并标记约7400万个数字，哪怕log log A很小（大概是5左右），总操作数也达到了7e7 * 5 = 3.5e8次，这比第一种算法实际执行的几万次操作多了整整一个数量级。
• 而且埃氏筛的内存访问模式是跳跃式的（比如标记i*j时，步长是i），当i较大时，缓存命中率会急剧下降，进一步拖慢执行速度——相比之下，第一种算法的素性检测是顺序循环，都是简单的整数取模运算，CPU执行效率极高。

3. 第二种算法的额外步骤雪上加霜 #

筛完素数之后，第二种算法还要再遍历一遍所有数字，把素数存入arr向量，最后再用双指针查找。这两步虽然复杂度是O(A)，但对于7e7的量级来说，又是几百万次的额外操作，进一步拉大了和第一种算法的时间差距。

总结 #

理论复杂度描述的是算法在最坏情况下的性能上限，但实际场景中，第一种算法利用了哥德巴赫猜想的特性，提前终止了遍历，真实开销远低于理论值；而第二种算法不管解在哪里，都必须先完成整个筛法的固定开销，最终导致大数值下反而更慢。

内容的提问来源于stack exchange，提问作者Tanay