1

时间复杂度是多少？为什么？

(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))
4

2 回答 2

3

mult 部分的时间复杂度可以这样找到：

要计算 (mult ab)，调用 (internal a accum) 直到 a = 1，所以我们有某种迭代 a 的尾递归（循环）。

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

(to-the-power-of mn) 也有一个 (internal x accum) 定义，它也循环 (直到 x = 0)

所以我们又有O(x)（= 线性时间复杂度）

但是：我们没有考虑内部函数调用所需的时间......
在内部，我们使用时间复杂度线性的（mult ab）定义，所以我们有以下情况：在第一次迭代中 mult调用时： (mult 1 m) --> O(1)
第二次迭代 这变成： (mult mm) --> O(m)
第三次迭代： (mult m² m) --> O(m*m) 和依此类推很明显，这会增长到 n = 0（或者在内部，这会变成 x = 0）

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

[编辑：]您还可以查看我之前提出的一个相关问题：Big O，您如何计算/近似它？这可能会给你一个线索，你可以如何更普遍地处理近似值

于 2008-10-30T09:25:37.217 回答
0

假设加法和乘法都算作一次运算，则此函数执行 O(m^n) 次运算。

首先考虑mult函数。它（mult ab）将执行 a-1 加法。因为，渐近增长是相同的，为了数学简单，让我们用 a 来近似它。

现在对于 to-the-power-of 函数，这对 mult 函数执行 n 次调用。这些调用是到 (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。

于 2008-10-30T09:23:53.273 回答