SICP的增长顺序定义中提到的常数是什么？

Question

第1.2.3节，程序的结构和解释 给出了以下成长顺序的正式定义：

我们说r(n(具有生长θ(f(n((，书面r(n(=θ(f(n(( (发音为" f(n(的theta"(，如果有正常数k 1 ，并且 k 2 独立于n，因此K _{1 f(n(≤r(n(≤k 2 f(n(对于任何足够大的n的值(换句话说，对于大n，将值r(n(夹在k 1 f(n(和k 2 f(n(之间。(}

常数k 1 和k ₂ 有什么意义？我很难将这个正式定义映射到现实世界的例子上，因为没有再次提及常数。

也许k 1 f(n(≤r(n(意味着有一些可观察到的生长？也许r(n(≤k ₂ f(n(表示f(n(是生长的上限吗？但是，如果r(n(=θ(f(n((和k 1 是一个正常数，那么k 1 f(n(何时小于r(n(？似乎只有当k 1 为1。

Answer 1

r和f是完全不同的函数，除了它们相对于n相对生长，因此没有理由f(n(等于r(n(。r是"该过程对于尺寸n的问题所需的资源数量"。F是无关的数学功能。

使θ的定义特别令人困惑的是，它不提及资源是r正在测量的，也不是使用资源的过程。

r(n(的示例可能是：

• 总结数字中使用的寄存器数量。
• 用于转码n GB的磁盘
• 发射N无人机花费的时间。

但是θ的定义不提及资源(寄存器，磁盘，时间(，也没有提及进程(总结，转编码或启动(。

如果我们的"过程"是一个称为P的软件程序，那么我们有三个完全不同的"函数"：

p(n) - a procedural function that programmers work with.
R(n) - a measuring function like ones used by engineers.
f(n) – a 'pure' mathematical function.

如果我们以阶乘过程为例，该过程具有θ(n(的生长，我们将拥有：

p(n) = (define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))
R(n) = The time in seconds for (factorial n) to complete.
f(n) = n  

r(n(= f(n(意味着(阶乘17(需要17秒的运行，这不太可能。

θ(n(的定义在说k₁和k₂存在，因此n足够大：

k₁ * n <= "Time taken for (factorial n) to run in seconds" <= k₂ * n

在现代计算机上，k₁需要很小的k₁ * n比实际的运行时间小。

对于树的斐波那契生长为θ(1.618ⁿ(，所以我们有：

p(n) = (define (fib n) (cond ((= n 0) 0) ((= n 1) 1)  (else ... )))
R(n) = The time in seconds for (fib n) to complete.
f(n) = 1.618ⁿ

的定义在说k₁和k₂存在：

k₁ * 1.618ⁿ <= "Time taken for (fib n) to run" <= k₂ * 1.618ⁿ)

(我已经使用" 1.618"作为黄金评分，而不是"φ"(