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

Question

假设我们有以下函数：

def modulo(a, b):
    """Take numbers a and b and compute a % b."""
    if b <= 0:
        return None
    div = int(a / b)
    return a - div*b

def power(a, b):
    """Take number a and non-negative integer b.
    Compute a**b."""
    if b == 0:
        return 1
    else:
        return a * power(a, b - 1)

对于modulo，大O符号是O(a / b)吗？因为执行所需的时间取决于 a 和 b 输入。但是，我在网上看到模数计算，其中大 O 符号是 O(logn)，所以不确定这是否适用于此。谁能澄清一下？

对于power，大O符号会不会是O(a^b)因为它涉及幂？

Answer 1

modulo 没有循环，它只是做常量时间运算（数学），所以它是 O(1)。 power 会将 b 减 1 直到它是 0，而函数的其余部分是 O(1)，所以它是 O(1*b) 或 O(b)。

Answer 2

按照前面回答的问题

时间复杂度是针对重复性任务计算的。因此，如果你一般没有循环，你就别谈时间复杂度了。你只是在应用一件事。

所以对于 modulo 你可以 'ignore it' (O(c)) c is a constant.

对于recursive function，因为我们每次都是重新进入函数，直到b==0，那么复杂度是O(b)类似于O(n)上一个问题。 (linear)

如果你 google Recursion 它会显示你 did you mean recursion 如果你一直点击它，它会一直把你带到同一个页面，因此，递归是一项重复性的任务。这就是为什么你认为它类似于一个循环。

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

Are these Big-O notations correct for simple modulus and power functions (Python)?

python

big-o

function