这种用于打印素数的算法的大O表示法是什么？

Question

我正试图弄清楚下面问题的时间复杂性。

import math
def prime(n):
for i in range(2,n+1):
for j in range(2, int(math.sqrt(i))+1):
if i%j == 0:
break
else:
print(i)
prime(36)

这个问题把素数打印到36。

我对上述计划的理解：对于每个n，内部循环运行sqrt(n(次，依此类推，直到n。

所以Big-o-旋转是o(n-sqrt(n((。

我的理解正确吗？如果我错了，请纠正我。。。

Answer 1

时间复杂性衡量随着输入的增加，数量或步骤(基本操作(的增加：

O(1)     : constant (hash look-up)
O(log n) : logarithmic in base 2 (binary search)
O(n)     : linear (search for an element in unsorted list)
O(n^2)   : quadratic (bubble sort)

要确定算法的精确复杂性，需要大量的数学和算法知识。你可以在这里找到它们的详细描述：时间复杂性

还要记住，这些值是为非常大的n值考虑的，所以根据经验，每当你看到嵌套的for循环时，想想O(n^2(。

您可以在内部for循环中添加一个steps计数器，并记录n的不同值的值，然后在图中打印关系。然后，您可以将您的图与n、log n、n * sqrt(n)和n^2的图进行比较，以确定算法的确切位置。