方案中acc函数的时间复杂度？
我一直试图找到该函数仅针对其中一个参数的严格限制时间复杂度。我认为它是 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))
I have been trying to find a tight bound time complexity for this function with respect to just one of the arguments. I thought it was O(p^2) (or rather big theta) but I am not sure anymore.
(define (acc p n)
(define (iter p n result)
(if (< p 1)
result
(iter (/ p 2) (- n 1) (+ result n))))
(iter p n 1))
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
@sarahamedani，为什么这是 O(p^2)？对我来说，它看起来像 O(log p) 。运行时应该对
n的值不敏感。您正在对一系列数字求和，从
n开始倒数。iter迭代的次数取决于p可以减半多少次而不小于 1。换句话说，就是最左边 '1' 位的位置p减一是iter迭代的次数。这意味着iter运行的次数与log p成正比。@sarahamedani, why would this be O(p^2)? It looks like O(log p) to me. The runtime should be insensitive to the value of
n.You are summing a series of numbers, counting down from
n. The number of timesiterwill iterate depends on how many timespcan be halved without becoming less than 1. In other words, the position of the leftmost '1' bit inp, minus one, is the number of timesiterwill iterate. That means the number of timesiterruns is proportional tolog p.您可以尝试观察它，或者更系统地了解它。假设我们从头开始这样做，我们应该尝试从函数定义构建递归关系。
目前，我们可以假设一个非常简单的机器模型，其中算术运算和变量查找都是常数时间。
令
iter-cost为计算计算iter所需步数的函数名称，并令其为p的函数，因为iter的终止仅取决于p。然后您应该能够为iter-cost(0)编写表达式。您可以对iter-cost(1)、iter-cost(2)、iter-cost(3)和执行此操作吗>迭代成本(4)？更一般地说，给定一个大于零的
p，你能表达iter-cost(p)吗？它将采用常量和对iter-cost的循环调用。如果您可以将其表达为递归形式，那么您就可以更好地以封闭形式表达它。You might try to eyeball it, or go from it more systematically. Assuming we're doing this from scratch, we should try build a recurrence relation from the function definition.
We can assume, for the moment, a very simple machine model where arithmetic operations and variable lookups are constant time.
Let
iter-costbe the name of the function that counts how many steps it takes to computeiter, and let it be a function ofp, sinceiter's termination depends only onp. Then you should be able to write expressions foriter-cost(0). Can you do that foriter-cost(1),iter-cost(2),iter-cost(3), anditer-cost(4)?More generally, given an
pgreater than zero, can you expressiter-cost(p)? It will be in terms of constants and a recurrent call toiter-cost. If you can express it as a recurrence, then you're in a better position to express it in a closed form.