对于计算次数随 n 波动的递归函数，Big-O 复杂度是多少？

Question

我有一个求指数的函数，但我对函数的复杂性感到困惑。

函数：

def expo(number, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        val = expo(number, exponent / 2)
        return  val * val
    else:
        return number * expo(number, exponent - 1)

我试着根据指数计算并绘制了计算次数的图表，得到了这样的结果： 图表： 指数：计算：

1:2, 2:3, 3:4, 4:4, 5:5, 6:5, 7:6, 8:5, 9:6, 10:6, 11:7, 12 : 6, 13 : 7, 14 : 7, 15 : 8, 16 : 6, 17 : 7, 18 : 7, 19 : 8, 20 : 7, 21 : 8, 22 : 8, 23 : 9, 24 : 7 , 25 : 8, 26 : 8, 27 : 9, 28 : 8, 29 : 9, 30 : 9

如您所见，计算次数在波动，我认为 Big-O 表示法不会是线性或二次的。我认为它会像一个多阶多项式，表示形式如

我是对的还是我对 O(n) 表示法的理解有误？

Answer 1

首先，你可以考虑最坏情况下的算法。因此，如果 T(n) 是算法的时间，最坏的情况是 T(n) = T(n-1) + c （c 是一个常量，用于比较、求和、调用函数...） .因此，T(n) = O(n).

另外，I think O(n) will not be linear or quadratic这个语句没有意义。如果一个函数在 O(n) 中，则意味着它至多是线性的。因此，它不可能是二次的。

现在您可以仔细检查时间复杂度计算并尝试找到复杂度的严格界限。因为，至少两次连续递归，我们将得到 exponent 的偶数（因为我们有 -1，如果 exponent 是奇数），因此，exponent 达到 1，最多计算 2 log(n)（因为在每 2 个连续递归中，指数将至少除以 2）。因此，T(n) 的紧界是 O(log(n)).

Answer 2

这是一种众所周知的算法，称为快速求幂（有时称为平方和乘法），其复杂度为 O(log(n))。维基百科有一整页：https://en.wikipedia.org/wiki/Exponentiation_by_squaring

但如果您不知道这些信息，一种思考方式是重写您的算法，以便您可以轻松找到递推公式。主要的困难是应用于奇数和偶数的不同程序。诀窍是将它们组合在一起，只进行一次递归调用。

def expo(number, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        val = expo(number, exponent / 2)
        return  val * val
    else:
        return number * expo(number, exponent - 1)  # exponent - 1 is even !

可以重写

def expo(number, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        val = expo(number, exponent / 2)
        return  val * val
    else:
        return number * expo(number, (exponent - 1) / 2) ** 2

现在您可以看到，在算法的每一步，exponent（大致）除以 2（这不再取决于它的奇偶校验），因此复杂度为 log(n)。

对于计算次数随 n 波动的递归函数，Big-O 复杂度是多少？

What will be Big-O complexity for a recursive function whose number of calculations oscillate with n?

python

algorithm

complexity-theory

big-o