Eratosthenes算法的筛选效率

Question

我试图理解"Eratosthenes的筛子".这是我的算法(下面的代码),以及我无法理解的功能列表(按顺序).

1. 为什么i * i效率更高i * 2？是的,我可以理解它会减少迭代次数,因此效率更高,但是它不会跳过一些数字(例如i = 9 => j = 81 skips 18 27 36 ...)？
2. 在维基百科上,我发现空间复杂度等于O(n)并且这是可以理解的; 无论我们输入什么数字,它都会创建一个输入大小的数组,但这里的时间复杂性让事情变得混乱.我发现了这种符号O(n(logn)(loglogn))- 那是什么？根据我的理解,我们有2次完整迭代和1次部分迭代O(n^2 * logn).

#include <iostream>
using namespace std;

int main() {
  cout << "Enter number:" << endl;

  int arrSize;
  cin >> arrSize;

  bool primesArr[arrSize];
  primesArr[0] = false;
  for (int i = 1; i < arrSize; i++) primesArr[i] = true;

  for (int i = 2; i < arrSize; i++)

    if (primesArr[i - 1]) {
      cout << i << endl;
   /* for (int j = i * 2; j < arrSize; j += i) less efficient */
      for (int j = i * i; j < arrSize; j += i)
        primesArr[j - 1] = false;
    }

  return 0;
}

Answer 1

为什么我*i比i*2效率更高？是的,我可以理解这将是更少的迭代,因此更有效率,但是它不会跳过一些数字(例如i = 9 => j = 81跳过18 27 36 ...)？

你指的是

for (int j = i * i; j < arrSize; j += i)

请注意,这i * i是循环计数器的初始值j.所以j大于的值i * i都将被标记出来.这是我们从跳过值i * 2到i * i已经先前迭代中划分出来.让我们考虑前几个:

当i == 2,我们标记所有2的倍数(2,4,6,8等).如果i == 3,如果我们开始j = 3 * 2 = 6那么我们将在达到9,12,15等之前再次标记6.由于6是2的倍数并且已经标记为关闭,我们可以直接跳到3 * 3 == 9.

当我们到达时i == 5,如果我们开始j == 5 * 2 == 10,那么我们将标记10,已经处理,因为它是2的倍数,15是3的倍数,20也是我们最终之前的2的倍数达到25,这不是任何小于5的底漆的倍数.

这里的时间复杂性让事情变得混乱.我发现这个符号O(n(logn)(loglogn)) - 这是什么？根据我的理解,我们有2次完整迭代和1次部分迭代,因此O(n ^ 2*logn).

您的分析得出该算法的正确结果O(n^2 * logn).更详细的分析可以证明更严格的上限O(n(logn)(loglogn)).请注意,它O(n(logn)(loglogn))是.的子集O(n^2 * logn).