这个方案的幂函数的时间复杂度是多少?

mult部分的时间复杂度如下所示:

要计算(mult a b),将调用(内部a acum),直到a=1 所以我们有一种尾部递归(循环),它在a上迭代。

因此我们知道(mult a b)的时间复杂度是 O(a) (=线性时间复杂度)

(m n的幂)也有一个(内部x accum)定义,它也循环(直到x=0)

我们又一次 O(x) (=线性时间复杂度)

但是 :我们没有考虑内部函数调用所需的时间。。。
在内部,我们使用(mult a b)定义,它在时间复杂度上是线性的,因此我们有以下情况: 在第一次迭代中,mult被调用为:(mult 1 m)——>O(1)
第二次迭代变成:(mult m)-->O(m)
第三次迭代:(mult m²m)-->O(m*m) 等等 很明显,它会一直增长到n=0(或者在内部,它会变成x=0)

因此,我们可以说,时间复杂度将取决于m和n: O(m^n)

[编辑:]你也可以看看我之前问过的一个相关问题: Big O, how do you calculate/approximate it? 这可能会给你一个更普遍地处理近似值的线索

假设加法和乘法都被算作一个运算,这个函数执行O(m^n)运算。

首先考虑多功能。它(mult a b)将精确执行a-1添加。因为,渐近增长是相同的,为了数学上的简单性,让我们用a来近似。

现在,对于函数的幂函数,它对mult函数执行n次调用。这些调用是到(mult 1 m),产生m,然后到(mult m m),产生m^2,然后到(mult m^2 m),产生m^3等等,直到m^n。所以这里执行的操作总数是m^0+m^1+…+这是(m^n-1)/(m-1),随着m^n的增长而增长。