algorithm - 对数运行时间和尾递归

Question

在学校里，我一直在学习运行时，并使用尾递归等编写更高效的算法，不久前，一项作业要求我们考虑计算幂的函数；

(define (exp x n)
    (if (zero? n) 1 (* x (exp x (- n 1)))))

我们的任务是编写一个运行时间为 O(log n) 的 exp 函数，所以这是我的答案:

(define (exp x n)
    (cond
        ((zero? n) 1)
        ((= 1 n) x)
        ((even? n) (exp (* x x) (/ n 2)))
        (else (* x (exp (* x x) (/ (- n 1) 2))))))

简单地来自 x^2n = (x^2)^n 和 x^2n+1 = x*(x^2)^n。

所以我一直在想办法实现尾递归来进一步优化这个功能，但是我真的想不出办法来做这件事。回到我的问题，有没有什么办法经验法则 知道何时可以将多项式运行时算法编写为对数运行时？

我问这个问题是因为，尽管以其运行时间是对数的方式编写它很容易，但如果没有特别要求，我绝不会想到这样做。

Answer 1

关于你的问题的第一部分:将过程变成尾递归形式相对简单，我们只需要传递一个额外的参数来累积答案。为了避免创建额外的过程，我将使用 named let :

(define (exp x n)
  (let loop ([x x] [n n] [acc 1])
    (cond
      ((zero? n) acc)
      ((= n 1) (* x acc))
      ((even? n) (loop (* x x) (/ n 2) acc))
      (else (loop (* x x) (/ (- n 1) 2) (* x acc))))))

对于第二个问题:经验法则是 - 如果在进行递归调用时有办法在某个时候将问题的大小减半(以这种方式可以相应地计算结果)，那么这是一个好兆头，表明它可能存在对数解。当然，这并不总是那么明显。