该方案幂函数的时间复杂度是多少？
时间复杂度是多少？ 为什么？
(define (mult a b)
(define (internal a accum)
(if (= a 1) accum
(internal (- a 1) (+ accum b))))
(internal a b))
(define (to-the-power-of m n)
(define (internal x accum)
(if (= x 0) accum
(internal (- x 1) (mult accum m))))
(internal n 1))
What is the time complexity? Why?
(define (mult a b)
(define (internal a accum)
(if (= a 1) accum
(internal (- a 1) (+ accum b))))
(internal a b))
(define (to-the-power-of m n)
(define (internal x accum)
(if (= x 0) accum
(internal (- x 1) (mult accum m))))
(internal n 1))
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
mult 部分的时间复杂度可以这样找到：
为了计算 (mult ab)，调用 (internal a accum) 直到 a = 1
所以我们有某种尾递归（循环）来迭代a。
因此我们知道 (mult ab) 的时间复杂度是 O(a) （= 线性时间复杂度）
（mn 次方）也有一个 (internal x accum) 定义，它也会循环（直到 x = 0），
所以我们再次有 O(x) （= 线性时间复杂度）
但是：我们没有考虑所需的时间内部函数调用...
在内部，我们使用 (mult ab) 定义，它的时间复杂度是线性的，所以我们有以下情况：
在第一次迭代中 mult 被调用： (mult 1 m) --> O(1)
第二次迭代变成： (mult mm) --> O(米)
第三次迭代：(mult m² m) --> O(米*米)
等等
很明显，它会一直增长，直到 n = 0（或者在内部变成 x = 0），
因此我们可以说时间复杂度取决于 m 和 n：O(m^n)
[编辑:] 你还可以看看我之前问过的一个相关问题：Big O ，你如何计算/近似它？这可能会给你一个线索，告诉你如何更普遍地处理近似值
the time complexity for the mult part can be found like this:
to calculate (mult a b), (internal a accum) is called until a = 1
so we have some kind of tail recursion (loop) that iterates over a.
we thus know that the time complexity of (mult a b) is O(a) (= linear time complexity)
(to-the-power-of m n) also has an (internal x accum) definition, that also loops (until x = 0)
so again we have O(x) (= linear time complexity)
But: we didn't take into account the time needed for the function calls of internal...
In internal, we use the (mult a b) definition which is linear in time complexity so we have the following case:
in the first iteration mult is called with: (mult 1 m) --> O(1)
second iteration this becomes: (mult m m) --> O(m)
third iteration: (mult m² m) --> O(m*m)
and so on
It is clear that this grows until n = 0 (or in internal this becomes x = 0)
thus we can say that the time complexity will depend on m and n: O(m^n)
[edit:] you can also take a look at a related question I asked earlier: Big O, how do you calculate/approximate it? which may give you a clue how you can handle the approximation more generally
假设加法和乘法都算作单个运算，则该函数执行 O(m^n) 运算。
首先考虑multi函数。 它 (mult ab) 将执行精确的 a-1 加法。 由于渐近增长是相同的，为了数学简单起见，让我们用 a 来近似它。
现在对于 to-of 函数，它执行 n 次调用 mult 函数。 这些调用是 (mult 1 m)，产生 m，然后是 (mult mm)，产生 m^2，然后是 (mult m^2 m)，产生 m^3，依此类推，直到 m^n。 所以这里执行的操作总数是 m^0 + m^1 + ... + m^n 之和。 这是 (m^n - 1) / (m-1)，其增长为 m^n。
Assuming addition and multiplication are both counted as a single operation, this function performs O(m^n) operations.
First consider the mult function. It (mult a b) will perform exactly a-1 additions. Since, the asymptotic growth is the same, lets approximate this by a, for mathematical simplicity.
Now for the to-the-power-of function, this performs n calls to the mult function. These calls are to (mult 1 m), yield m, then to (mult m m), yielding m^2, then to (mult m^2 m), yielding m^3 and so on upto m^n. So the total number of operations performed here is the sum m^0 + m^1 + ... + m^n. This is (m^n - 1) / (m-1) which grows as m^n.