O(log(n)) 是这个函数的正确 Big O 表示法吗？

Question

我编写了一个函数来确定给定数字是否为质数。我有以下代码

def prime(n):
    if n == 1:
        return n
    elif n > 1: 
        for i in range(2, (1+floor(sqrt(n)))):
            if n % i == 0:
                return False
        return True

我"calculated"大O表示法是O(log(n))，但我不确定它是否正确。

Answer 1

取模、floor、sqrt都是O(1)时间。 Python 中的大多数基本算术和数学运算的运行时间为 O(1)。

决定运行时间的最相关因素是循环（或嵌套循环）。

在这种情况下，你有

for i in range(sqrt(N))

这意味着您的程序将不得不执行循环内的所有内容 sqrt(N) 次。这将为您提供 O(sqrt(N)).

的运行时间

Answer 2

Modulo 不是 O(log(n))，它只是标准整数除法的一部分，并且是 O(1)。您正在进行 sqrt(n) 次迭代，因此它是 O(sqrt(n))。如果模实际上是 O(log(n) 你的结果将是 O(sqrt(n)log(n)) 而不是 O(log(n)) 因为它重复了 sqrt(n) 次。Floor 肯定是 O(1)，sqrt 取决于实现，但我'我很确定它会是 python 中的 O(1)。

如果您有两个单独的循环：一个使用 O(sqrt(n))，另一个使用 O(n^2)，那么整个算法将是 O(n^2)，因为 n^2 比 [=] 增长得快得多11=] 并且您将两者相加而不是相乘。当你在另一个循环中有一个循环时，你乘法，如果它们彼此跟随，你将它们相加，你不能丢弃乘法中增长较慢的部分。

O(log(n)) 是这个函数的正确 Big O 表示法吗？

Is O(log(n)) the correct Big O notation for this function?

python

big-o