scheme - 方案中 acc 函数的时间复杂度？

Question

我一直在尝试仅针对其中一个参数为该函数找到一个严格的时间复杂度。我以为是 O(p^2) （或者相当大的 theta），但我不确定了。

(define (acc p n)
  (define (iter p n result)
    (if (< p 1) 
        result
        (iter (/ p 2) (- n 1) (+ result n))))
  (iter p n 1))

Answer 1

@sarahamedani，为什么会是 O(p^2)？对我来说，它看起来像 O(log p)。运行时应该对 的值不敏感n。

您正在对一系列数字求和，从 开始倒数n。迭代的次数iter取决于在p不小于 1 的情况下可以减半的次数。换句话说， 中最左边的“1”位的位置p减一，就是iter迭代的次数。这意味着iter运行次数与 成正比log p。

Answer 2

您可能会尝试关注它，或者更系统地从它开始。假设我们从头开始这样做，我们应该尝试从函数定义中构建递归关系。

目前，我们可以假设一个非常简单的机器模型，其中算术运算和变量查找是常数时间。

让iter-cost是计算需要多少步计算的函数的名称iter，并让它成为 的函数p，因为iter的终止仅取决于p。然后你应该能够为 编写表达式iter-cost(0)。你可以为iter-cost(1), iter-cost(2),iter-cost(3)和做到这一点iter-cost(4)吗？

更一般地，给定一个p大于零的值，你能表达iter-cost(p)吗？它将根据常量和对iter-cost. 如果您可以将其表达为重复，那么您可以更好地以封闭形式表达它。