SICP对增长顺序的定义中提到的常数是什么？
在1.2.3节中，程序的结构和解释给出了增长顺序的正式定义：
我们说R（n）具有生长阶数Θ（f（n）），写成R（n）=Θ（f（n））（发音为“the（f（n）”），如果有正常数k 1以及k 2 n无关，使得k的1 F（N）≤R（n）的≤ķ 2 F（N）对于n的任何足够大的值。（换句话说，对于大的n，值R（n）夹在k 1 f（n）和k 2 f（n）之间。）
常数k 1和k 2的意义是什么？我在将这个正式定义映射到现实世界的例子时遇到了麻烦，因为常量不再被提及。
也许k 1 f（n）≤R（n）意味着有一些可观察到的增长？也许R（n）的≤ķ 2 F（N）是指F（n）是生长的上限？但是如果R（n）=Θ（f（n））并且k 1是正常数，那么k 1 f（n）何时小于R（n）？似乎只有当k 1为1 时条件才成立。
回答 1
Stack Overflow用户
发布于 2019-05-09 14:34:08
据我了解，增长的顺序是资源使用增长的广泛近似。k 1和k 2表示近似值需要有多宽。它们可以根据需要小到大，我们不需要知道它们的价值，我们只需要知道它们的存在。
例如，如果我们有R（n）=Θ（n²），那么我们不期望R（2 * n）恰好是4 * R（n）。k 1和k 2给出了它可以变化多少的限制。也许k 1 = 0.01和k 2 = 100就足以知道当n加倍时：
0.01 * 4*R(n) <= R(2*n) <= 100 * 4*R(n)
但它必须是'永远'，例如，如果我们有1000 * n
0.01 * 1,000,000 * R(n) <= R(1000*n) <= 100 * 1,000,000 * R(n)
如果存在k1和k2（无论它们是小还是大），那么我们知道R（n）将始终使用比Θ（n）函数更多的资源，并且最终将使用比Θ（n³）函数更少的资源。
例：
假设n是我们传递给过程的数字项，我们关注的资源是过程完成所需的时间。我们假设阶数增长是Θ（n²），100是n的足够大的值。
处理100件物品所需的实际时间是8秒。换一种说法：
Actual: R(100) = 8
知道R（n）=Θ（n²）我们现在可以估计如果我们用更多项目调用它将需要多长时间：
With n = 100 items
Estimates of Time that Would be Taken
=====================================
Estimate of R(200) = R(2*n) = (2^2)*R(n) = 32s
Estimate of R(1,000) = R(10*n) = (10^2)*R(n) = 800s
Estimate of R(10,000) = R(100*n) = (100^2)*R(n) = 80,000s
Estimate of R(100,000) = R(1,000*n) = (1,000^2)*R(n) = 8,000,000s
Estimate of R(1,000,000) = R(10,000*n) = (10,000^2)*R(n) = 800,000,000s
每次物品的数量增加10倍，所以花费的时间就会增加100倍。
因此在计算估计值时根本不使用k1和k2。k1和k2用于形式化实际值与估计值的差异。如果这确实是一个Θ（n²）程序，那么：
k1 * estimate <= actual <= estimate * k2
对于某些k1和k2来说总是如此。
例如，对于非常平滑，可预测的函数k1 = 0.9和k2 = 1.1可能就足够了，那么我们知道：
Limits of Actual Time Taken
===========================
R(200) is always is in the range: 28.8 - 35.2
R(1,000) is always is in the range: 720 - 880
R(10,000) is always is in the range: 72,000 - 88,000
R(100,000) is always is in the range: 7,200,000 - 8,800,000
R(1,000,000) is always is in the range: 720,000,000 - 880,000,000
对于一个非常粗略，不太可预测的函数，我们需要得到k1 = 0.001和k = 1,000，我们得到：
Limits of Actual Time Taken
===========================
R(200) is always is in the range: 0.032 - 32,000
R(1,000) is always is in the range: 0.8 - 800,000
R(10,000) is always is in the range: 80 - 80,000,000
R(100,000) is always is in the range: 8,000 - 8,000,000,000
R(1,000,000) is always is in the range: 800,000 - 800,000,000,000
因此，如果k1和k2彼此接近（我们有可靠的可预测增长），那么这是一个实用的，有用的估计。但是如果k1和k2需要非常不同（因为我们有更多的不规则增长），那么估计就不是很有用了。但两者都被认为具有Θ（n²）增长。
当然，如果我们找不到任何满足上述条件的k1和k2那么它就不是Θ（n²）。
（我已经简化了一点。如果k1和k2彼此接近，那么它们将是0.0008的一侧，这是你需要将项目^ 2乘以获得总时间所需的值（例如，对于100个项目，时间是100 * 100 * 0.0008 = 8秒））。
https://stackoverflow.com/questions/-100009028
复制相似问题