你如何计算增长的综合订单？

Question

假设我有一个带有形参 p 的递归过程。这个程序

将递归调用包装在 Θ(1)（延迟）操作中
并在该调用之前执行 Θ(g(k)) 操作。

k 取决于 p 的值。 [1]

该过程使用参数 p/b 调用自身，其中 b 是一个常量（假设它在某个时间点终止1 和 0) 之间的范围。

问题 1。如果 n 是初始调用过程中 p 的参数值，那么 [=170= 的增长顺序是什么？ ] 和执行的步骤数，根据 n，对于此过程生成的过程

if k = p? [2]
如果k = f(p)？ [3]

脚注

[1] 即，根据传递给 p 的参数值。
[2] 即，嵌套操作的输入大小与我们的过程相同。
[3] 即，嵌套操作的输入大小是我们过程的输入大小的函数。

示例程序

(define (* a b)
  (cond ((= b 0) 0)
        ((even? b) (double (* a (halve b))))
        (else (+ a (* a (- b 1))))))

此过程根据规则

执行整数乘法作为重复加法

a * b = double (a * (b / 2)) 如果 b 是偶数
a * b = a + (a * (b - 1)) 如果 b 是奇数
a * b = 0 如果 b 为零

伪代码：

define *(a, b) as
{
    if (b is 0) return 0
    if (b is even) return double of *(a, halve (b))
    else return a + *(a, b - 1)
}

这里

形参为b.
递归调用的参数是b/2。
double x 是一个 Θ(1) 运算，类似于 return x + x。
halve k 是 Θ(g(k)) 和 k = b 即 Θ(g(b)).

问题 2。当评估 *(a, n) 时，根据 n，增长的顺序是什么？

在你回答之前

请注意，主要问题是问题 1 的两个部分。

问题2可以作为第一部分回答。对于第二部分，您可以假设 f(p) 是您喜欢的任何函数：log p, p/2、p^2 等

Answer 1

您需要应用麦汁案例分析。

首先，您可以使用二的幂来近似解决方案：

如果 $b=2^n$ 那么显然算法采用： $\Theta(n* g(k))$ （其中 $n=log b$ ）。

如果是奇数那么应用-1后得到偶数除以2，只能重复 $log b$ 次，步数也是 $\Theta(log b * g(k))$ , b 是奇数的情况显然是最坏的情况，这给了你答案。

（我认为您需要一个额外的基本案例：b=1）

Answer 2

看到有人回答了问题2，所以我只回答问题1。

首先要注意的是问题的两个部分是等价的。在第一个问题中，k=p 所以我们对某些函数执行 Θ(g(p)) 操作 g。在第二个中，k=f(p) 我们执行 Θ(g(f(p))) = Θ((g∘f)(p ))。将第一个问题中的 g 替换为 g∘f ，第二个问题就解决了。

因此，我们只考虑第一种情况，即k=p。用 T(n) 表示递归过程的时间复杂度，我们有：
T(n) = T(n/b) + g(n) [自由项要乘以一个常数c,但我们可以讨论 "amount of c's" 中的复杂性并且 theta 边界显然将保持不变]

递推公式的解为T(n) = g(n) + g(n/b) + ... + g(n/b^i) + ... + g(1)
除非给出关于 g 的额外信息，否则我们无法进一步简化它。例如，如果 g 是一个多项式，g(n) = n^k，我们得到
T(n) = n^k * (1 + b^-k + b^-2k + b^-4k + ... + b^-log(n)*k) <= n^ k * (1 + b^-1 + b^-2 + ....) <= n^k * c 对于常量 c，因此 T(n) = Θ(n^k)。

但是，如果 g(n) = log_b(n)，[从现在开始我忽略日志的基础]我们得到 T(n) = log(n) + log(n/b) + ... + log(n/(b^log_b(n))) = log(n^log(n ) * 1/b^(1 + 2 + ... log(n))) = log(n)^2 - log(n)^2 / 2 - log(n) / 2 = Θ(log(n) ^ 2) = Θ(g(n)^2).

你可以很容易地证明，使用类似于 g 是多项式的证明，当 g = Ω(n) ，即至少是线性的，那么复杂度就是g(n)。但是当 g 是次线性时，复杂度可能比 g(n) 大得多，因为 g(n/b ) 可能比 g(n) / b.

大得多

你如何计算增长的综合订单？

How do you calculate combined orders of growth?

complexity-theory

time-complexity

space-complexity

脚注

示例程序

在你回答之前