对于计算次数随 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)我尝试根据指数计算并绘制计算次数图并得到以下结果： Graph: Exponent : Calculations: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

这是一种众所周知的算法，称为快速求幂（有时是平方和乘法），其复杂度为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).

Answer 2

首先，您可以考虑最坏情况的算法。因此，如果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))。