这些 Big-O 符号对于简单的循环函数 (Python) 是否正确？

Question

假设我们有以下两个函数：

def is_prime(x):
    """Take an integer greater than 1 and check if it is a prime number."""
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            return False
    return True

def multiply(a, b):
    """Take two integers and compute their product."""
    res = 0
    for i in range(1, b + 1):
        res += a
    return res

is_prime 的 Big-O 表示法是 O(c) 而 multiply 是 O(n) 是正确的吗？

我有点困惑，因为我认为循环在复杂性方面至少是 O(n)，但是使用 is_prime 函数，它只需要一个输入并计算一个结果，这我不认为它的大小会有所不同？感谢澄清以更好地理解简单函数上的 Big-O 表示法。

Answer 1

Is it correct to say that the Big-O notation for is_prime is O(c) and multiply is O(n)?

没有

让我们采用第一个算法。

for i in range(2, int(x**0.5) + 1):

被执行了 sqrt(x) - 1 次，因为 for 循环从 2 开始。所以复杂度是 O(sqrt(x)).

让我们采用第二个算法。

for i in range(1, b + 1):

被执行了b次。所以复杂度是 O(b)

Answer 2

大O

对于第一个循环，如我的评论 O(sqrt(x)) 中所述，因为您要循环从某个范围到最大值 sqrt(x)+c 的数字，其中 c 是常数。

由于循环中的内容不会影响循环过程，因此时间复杂度保持不变。

与第二个类似，您从 range(1,b+1) 开始循环，即 O(b+1) = O(b)。 b 增长得越多，您的算法实现其目的所需的时间就越多。 (Linearity).

但是，例如，如果循环受到循环内发生的任何事情的影响，复杂性可能会改变。

类似于第一个循环的简单示例

b=50
for i in range(1,b):
    if i> b**0.5:
        break
    else:
        print(i)

此循环基于条件的复杂度为 O(sqrt(b))。换句话说，不要只阅读 for... 行并假设复杂性。

Answer 3

如果不解释确切“n”是什么以及确切你在数。

您还需要说明您是在讨论 space 复杂度、步骤复杂度还是时间复杂度，以及您是在讨论最佳情况、预期情况、平均情况、摊销的最坏情况还是最坏情况案例.

让我们从头说起。通常，我们将复杂性表示为输入的 length 的函数。这很重要，因为在这里，输入是 numbers，而数字的 length 当然不是 value 而不是位数。然而，正如我们稍后将看到的，在这种特殊情况下实际上更方便地查看数字本身的值。这样做是完全允许的，我们只需要清楚地定义我们在谈论什么。

此外，假设我们对 步复杂度 感兴趣（不是时间复杂度或 space 复杂度）并且我们对 最坏情况.

最后，我们需要定义我们正在计算的是什么，所以假设我们正在计算固定大小整数的“原始操作”。（其中“原始操作”为 +、-、*、/、%、&、|、^、~）。我们将假设这些原始操作采取有限数量的步骤，受某个常数的限制。

好的，现在我们已经定义了我们感兴趣的东西（最坏情况下的步骤复杂度）、我们正在计算的东西（对固定大小整数的原始操作）以及“n”是什么（value），我们可以去仔细看看算法。

在is_prime中，for循环在最坏情况下迭代从2到floor(sqrt(x)+1)不包括范围内的项目。（这里最坏的情况是数字 x 是素数。）因此，循环体最多执行 floor(sqrt(x)) 次。

但是，我们还需要查看循环体的内容。 The step complexity of the modulo operation a % b is O(length(a)) 或 O(log_2 a).

所以，总共，is_prime(x)的最坏情况步复杂度是O(floor(sqrt(x)) * log_2 x)固定大小整数的原始操作，或简化一点 O(sqrt(x) * log x).

我们可以对multiply做类似的分析：循环执行了b次。循环体由一个加法组成。 add(x, y) has a worst-case step complexity of O(length(x + y))，或O(max(length(x), length(y)))，或O(length(max(x, y)))，或O(log_2(max(x, y))).

所以，在 循环的每个 次迭代中，成本是 O(log_2(max(res, a)) ).由于在循环的第二次迭代后 res 总是大于 a，我们可以将其简化为 O(log_2(res)) 或 O(log (a * i)).

因此，总时间复杂度为 O(SUM[log_2(a * i) over i 从 1 到 b])，其中 according to Wolfram Alpha O(log(a^b * Pochhammer[1, b]))，其中 Pochhammer 符号 是 上升阶乘 .

不幸的是，我真的不知道如何进一步简化它。我们可以做的是退后一步，对循环体做出最坏情况假设：最坏情况是最后一次迭代，其中res = (b-1) * a，因此加法大约需要 O(log(b * a))。那么我们可以说 multiply 是 O(b * log(b * a)) 或 O(b * (log b + log a))，我们知道这是高估。

另请注意，到目前为止我们完全忽略了循环的每次迭代都有一个隐藏操作：我们需要分配数字i。分配数字是O(length(i)) 或O(log_2 i)。我将把这个操作作为练习，但请注意，例如，对于 is_prime，它还涉及 Pochhammer 符号。

请注意，步骤复杂性如此复杂并不特别令人惊讶。例如，如果您查看 the time complexities of various well-known multiplication algorithms on Wikipedia，您还会看到类似 O(n^{^{log 2k-1}/_{log k}}) for k-way Toom-Cook multiplication, 其中n是长数的位数，k是算法的参数。

这些 Big-O 符号对于简单的循环函数 (Python) 是否正确？

Are these Big-O notations correct for simple loop functions (Python)?

python

big-o

loops