用于寻找素数的算法的大 O

Question

我有一个来自大学的伪代码：

(0) initialize logic array prim[ n ]
(1) prim[ 1 ] = false
(2) for i = 2 to n do
(3)   for k = 2 to i − 1 do
(4)     if i % k == 0 then
(5)       break
(6)     prim[i] = (k == i) // Was loop (3) fully executed?
(7) return prim[]

现在我必须计算这个伪代码的大 O。

我们学会了一步步做，把操作次数加起来。

这是我目前得到的：

比较：

(4): (n-1)(n-2) outer loop * inner loop
(6): (n-1) outer loop

(4) + (6): n^2 - 2 n + 1 operations for all comparisons

作业：

(1): 1
(6): (n - 1)

(1) + (6): n operations for all assignments

部门：

(4): (n-1)(n-2) outer loop * inner loop

n^2 - 3 n + 2 operations for the division.

因此，如果您将这些数字加起来：

(n^2 - 2 n + 1) + n + n^2 - 3 n + 2 = 2n^2 - 4 n + 3

我认为我这边的某个地方存在误解，因为大 O 应该是 O(n^2)，但根据我的理解，这里是 O(2n^2)。

你们能帮我弄清楚我的误解是什么吗？谢谢

Answer 1

你的误解是认为 2n^2 不是 O(n^2)。 Big-O 忽略缩放常数，所以你可以忽略前面的 2。

Answer 2

其实你已经答对了！

那是因为 O(2*n²) 等于 O(n²)。常量乘数不影响 Big-O。有关其背后数学原理的更多信息，我建议阅读 Asymptotic Analisys。为了简单起见，它与 n 趋于无穷大的时间有关。

Answer 3

内循环计算错误：

当外循环 (i) 从 2 到 n 时，内循环将迭代不超过 0 + 1 + 2 + ... + n-2 次，等于前 n- 2个自然数。

前n个自然数之和的公式为n*(n+1)/2。

由于偏移量为 -2，因此内循环的最大迭代次数为 (n-2) * (n-1) / 2。

用于寻找素数的算法的大 O

Big O for an algorithm for finding prime numbers

c++

algorithm

big-o

primes