O(log(n))是这个函数的正确大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

我 "计算 "出大O的符号是O(log(n))，但我不确定是否正确。

Answer 1

Modulo、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)。

如果你有两个sepearate循环：一个用 O(sqrt(n)) 和另一个有 O(n^2) 那么整个阿尔戈就会是 O(n^2) 因为 n^2 增长速度远远超过 sqrt(n) 而你是将两者相加而不是相乘。当你在另一个循环里面有一个循环的时候，你就会乘法，如果它们互相跟随，你就把它们加起来，你不能把乘法中增长较慢的部分丢掉。