什么是增长顺序以及如何计算它？
What is Order of Growth and How do you compute it?
为什么我要问这个问题
最近开始看sicp，工作了
我通过 Section 1.2.3 的方式。
我无法理解 Order of Growth 的一些细节。请多多包涵
我的问题太长了。另请注意，我以前从未处理过分析算法。
我在 Sicp 中读到的内容以及我对它的看法
以下是 Sicp 中的几段文字：
n 是哪个确切值？
Let n be a parameter that measures the size of the problem. In our previous examples we took n to be the number for which a given
function is to be computed, but there are other possibilities. For instance,
if our goal is to compute an approximation to the square root of a number,
we might take n to be the number of digits accuracy required.
采用 Section 1.7 中给出的以下步骤求牛顿平方根：
(define (sqrt x)
(sqrt-iter 1.0 x))
这是(sqrt-iter)
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
其中 good-enough? 检查 guess 是否足够好近似
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
现在按照Sicp，0.001应该是n，但是(sqrt x)不应该输入n吗？
迭代次数根据输入变化x，即需要的迭代次数
会根据数字的大小而改变。
这是我的 python 等效证明：
In [33]: sqrt(2)
1
1.5
1.4166666666666665
achieved 1.4142156862745097 in 3 iterations
In [34]: sqrt(4)
1
2.5
2.05
2.000609756097561
achieved 2.0000000929222947 in 4 iterations
In [35]: sqrt(1024)
1
512.5
257.2490243902439
130.61480157022683
69.22732405448895
42.00958563100827
33.19248741685438
32.02142090500024
achieved 32.0000071648159 in 8 iterations
所以 0.001 不应该是 k1 或 k2，因为它是一个恒定且独立的值的
n（这里是我们输入的值sqrt）?
R(n)不是常数吗？
let R(n) be the amount of resources the process requires for a problem of size n. R(n) might
measure the number of internal storage registers used, the number of elementary machine operations performed, and so on. In computers that
do only a fixed number of operations at a time, the time required will be
proportional to the number of elementary machine operations performed.
这里，Sicp 说 R(n) 可能是执行的基本操作数，但是
从 OS 到 OS 执行的操作数不是不同吗？作为 Linux 机器可能
执行一组特定的步骤，一台 FreeBSD 机器，另一台 Windows 机器？
你很快就会明白我为什么这么说了。
增长顺序
We say that R(n) has order of growth Θ(f (n)), written R(n) = Θ(f (n)) (pronounced “theta of f (n)”), if there are positive constants k1 and k2 independent of n such that k1 f (n) ≤ R(n) ≤ k2 f (n) for any sufficiently large value
of n. (In other words, for large n, the value R(n) is sandwiched between
k1 f (n) and k2 f (n).)
现在，根据我的理解，我们通过做一些代数来计算使用的资源的增长
从函数 R(n) 和 f(n) 接收值（R 是一个函数吗？和 f 我在想什么？我不知道！）
阶乘和斐波那契数列的例子
For instance, with the linear recursive process for computing factorial
described in Section 1.2.1 the number of steps grows proportionally to the
input n. Thus, the steps required for this process grows as Θ(n). We also
saw that the space required grows as Θ(n). For the iterative factorial, the
number of steps is still Θ(n) but the space is Θ(1)—that is, constant. The
tree-recursive Fibonacci computation requires Θ(ϕn) steps and space Θ(n),
where ϕ is the golden ratio described in Section 1.2.2.
现在这是对我来说毫无意义的部分 - 我认为这是一个步骤吗？
我是否考虑使用替换模型的替换次数？
或者我是否考虑评估的表达式数量？或者我考虑什么时候
计算算术？
我知道 space 在递归过程和迭代中是 Θ(n)（因为解释器每次递归都需要多记住一件事）和迭代 Θ(1)（作为解释器x 的一些值并继续。）我不明白斐波那契计算（树递归）如何采用 Θ(n)。
我也不知道前面的n和步数有什么关系
我的问题
下面是我所有关于增长顺序的问题列表：
算法中n的确切值是什么？
R(n)会发生什么？ （当然假设它是一个函数） n divide/multiply 是一个值吗？
我认为一个步骤是什么？
如何计算步骤的增长顺序和 space。
简而言之：
什么是增长阶数，如何计算它？
你问的是一个很长的话题。我会尽量简短地回答。然而，这是一个基本的计算机科学概念，在任何算法书籍的开头，您都会找到有关增长顺序的章节（又名 Big-O、Big-Omega 和 Big-theta 符号） .如果您有兴趣，我强烈推荐这本书：https://www.amazon.ca/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844
为了回答您的问题，科学家们无法比较他们的代码，因为原子操作在不同的机器上需要不同的时间。有很多因素会影响代码在机器上的 运行 时间，例如 OS 负载、OS 调度、在 CPU 上实现的原子操作等。因此他们提出了具有增长顺序的理论定义。
有一件事肯定会影响 运行 时间，那就是代码输入的大小，通常由 n 指出。由于 n 可能非常大，这些符号也称为渐近符号。所以，当我们谈论增长顺序时，我们假设 n 是任意大的（我们不关心小的输入大小）。简单地说，增长顺序是您的程序执行的原子步骤数（也称为基本步骤）。什么是原子？任何需要 1 或 2 或常数 CPU 操作的操作（常数，我的意思是它不依赖于 n，输入大小）。让我举一个例子。
此代码：
c = a + b
有一个原子步骤，它有求和和赋值。
另一个例子：
for i in 1..n:
print(i)
此代码有一个原子步骤 print(i) 并重复 n 次（令 n 为输入大小）。所以我们说这个程序有n个原子操作（即它的增长顺序是O(n)）。
那么，到目前为止，我希望您了解什么是原子操作以及什么是增长顺序（原子步数）。然而，通常情况下，计算增长顺序并不容易，涉及到大量的数学运算。例如，此代码：
for i in 1..n:
for j in i..n:
print(i+j)
在这段代码中，由于 j 依赖于 i，我们将进行 n + (n-1) + ... + 1 = n*(n+1)/2 原子操作。如果您计算该公式，它是 n^2 + ...。由于 n^2 在结果中有最大的指数，我们只关心那个项。在非常大的输入尺寸中，该项占主导地位，我们称其增长顺序为 O(n^2)（我知道缺少很多细节）。
因此，当我们说程序 A 的增长顺序为 O(n) 并且程序 B 的增长顺序为 O(n^2) 时，我们可以肯定，对于较大的输入大小，程序 B 会慢得多比程序 A（我们终于可以在机器上比较没有 运行 的代码）。
所以总而言之，增长的顺序是当输入大小非常大时原子操作的数量，我们不关心小操作，我们只关心最大的操作块。
我在这里的话可能会冒犯科学家和工程师。致我的科学家朋友们：当我在这里解释增长顺序时，我在数学上并不准确（如果您关心确切的数学定义，请阅读我提到的那本书）。致我的工程师朋友：是的，科学家在计算时忽略的那些小步骤 Big-o 实际上在实践中很重要，但科学家需要简化以建立基础，然后再讨论细节。
如果您想编写有效的代码，您必须了解算法的增长顺序。互联网上有很多关于这个主题的优秀资源，有些在数学上比其他的更准确，但这是我自己在数学上不准确的解释：
假设您有一些数据，例如来自数据库的 100 行，您想要处理它。现在，您实际上可以用这些数据做什么？
也许您只想打印第一行。这有多难？好吧，不是很难。你只需要一个操作就可以打印（first_row）。如果你有 1000 行，你仍然可以只用一个操作打印第一行，这种情况意味着无论你处理多少数据，它仍然会花费你相同（恒定）的时间，O(1).
然后我们有另一个非常重要的增长顺序O(log(n))。这对于在排序数据中搜索的算法来说是典型的。如果您有 100 行已排序的名称，并且您正在寻找某个名称，则只需要进行几次比较。通过每次比较，您将数据切成两半，并在 6 次操作中找到最坏情况下的名称。如果您正在查看 1000 个排序的行，则大约需要 9-10 次比较。这在大数据搜索中非常有效，您不必担心在排序数据的大数据集中搜索。总会很快的。
现在，如果您想打印所有数据，则必须在每一行上调用 print。对于 100 行，您必须执行 100 次操作，对于 1000 行，您必须执行 1000 次操作。这意味着您需要的工作量与您正在处理的数据量成正比。这将是 O(n).
O(n*n) 是您尝试在数据中查找重复行的示例。为此，您需要将每一行与其他每一行进行比较。所以你必须对 100 行进行 10000 次比较，对 1000 行进行 1000000 次比较！正如您在本例中看到的那样，所需的操作数量开始快速增长，并且这种增长可能会限制您在现代计算机上几秒钟内可以处理的数据量（您通常想要的）。这就是为什么当您看到两个 for 循环相互结合时，您必须开始小心。这也称为多项式增长。
O(e^n) 是指数增长，而且增长非常非常非常...非常快。考虑这样一种情况，您有 100 行随机数。如果您要找到总和为 50 的这些数字的所有子集，则需要大约 1267650600228229401496703205376 操作。对于 1000 行，它将是一个包含 300 个零的数字。对于作为程序员的您来说，这意味着如果您尝试像这样处理 1000 个数字，您将永远得不到结果。
O(n!) 是一个阶乘复杂度，它增长得更快，你不会用这种算法处理任何大数据集。一个典型的例子是使用 brute-force 搜索解决旅行商问题。这意味着如果有 100 行包含 100 个城市并且您想知道访问它们的顺序是什么，那么您将采用最短的路径来计算每种可能的旅行组合的距离并且它将意味着用 157 个零执行许多操作，对于 1000 个城市，该数字将有数千个零。这是一个你无法想象的疯狂数字。考虑一下宇宙中大约有 10^78 到 10^82 个原子！换句话说，您可以在计算机上针对几个城市优化销售员的路径。
您应该能够根据增长的速度对增长的顺序进行排序。将其绘制成图形并在编写某些算法时以及何时发现自己时始终考虑这幅图会很有帮助将一个循环放入另一个循环。
为什么我要问这个问题
最近开始看sicp，工作了 我通过 Section 1.2.3 的方式。 我无法理解 Order of Growth 的一些细节。请多多包涵 我的问题太长了。另请注意，我以前从未处理过分析算法。
我在 Sicp 中读到的内容以及我对它的看法
以下是 Sicp 中的几段文字：
n 是哪个确切值？
Let n be a parameter that measures the size of the problem. In our previous examples we took n to be the number for which a given function is to be computed, but there are other possibilities. For instance, if our goal is to compute an approximation to the square root of a number, we might take n to be the number of digits accuracy required.
采用 Section 1.7 中给出的以下步骤求牛顿平方根：
(define (sqrt x)
(sqrt-iter 1.0 x))
这是(sqrt-iter)
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
其中 good-enough? 检查 guess 是否足够好近似
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
现在按照Sicp，0.001应该是n，但是(sqrt x)不应该输入n吗？
迭代次数根据输入变化x，即需要的迭代次数
会根据数字的大小而改变。
这是我的 python 等效证明：
In [33]: sqrt(2)
1
1.5
1.4166666666666665
achieved 1.4142156862745097 in 3 iterations
In [34]: sqrt(4)
1
2.5
2.05
2.000609756097561
achieved 2.0000000929222947 in 4 iterations
In [35]: sqrt(1024)
1
512.5
257.2490243902439
130.61480157022683
69.22732405448895
42.00958563100827
33.19248741685438
32.02142090500024
achieved 32.0000071648159 in 8 iterations
所以 0.001 不应该是 k1 或 k2，因为它是一个恒定且独立的值的
n（这里是我们输入的值sqrt）?
R(n)不是常数吗？
let R(n) be the amount of resources the process requires for a problem of size n. R(n) might measure the number of internal storage registers used, the number of elementary machine operations performed, and so on. In computers that do only a fixed number of operations at a time, the time required will be proportional to the number of elementary machine operations performed.
这里，Sicp 说 R(n) 可能是执行的基本操作数，但是 从 OS 到 OS 执行的操作数不是不同吗？作为 Linux 机器可能 执行一组特定的步骤，一台 FreeBSD 机器，另一台 Windows 机器？ 你很快就会明白我为什么这么说了。
增长顺序
We say that R(n) has order of growth Θ(f (n)), written R(n) = Θ(f (n)) (pronounced “theta of f (n)”), if there are positive constants k1 and k2 independent of n such that k1 f (n) ≤ R(n) ≤ k2 f (n) for any sufficiently large value of n. (In other words, for large n, the value R(n) is sandwiched between k1 f (n) and k2 f (n).)
现在，根据我的理解，我们通过做一些代数来计算使用的资源的增长
从函数 R(n) 和 f(n) 接收值（R 是一个函数吗？和 f 我在想什么？我不知道！）
阶乘和斐波那契数列的例子
For instance, with the linear recursive process for computing factorial described in Section 1.2.1 the number of steps grows proportionally to the input n. Thus, the steps required for this process grows as Θ(n). We also saw that the space required grows as Θ(n). For the iterative factorial, the number of steps is still Θ(n) but the space is Θ(1)—that is, constant. The tree-recursive Fibonacci computation requires Θ(ϕn) steps and space Θ(n), where ϕ is the golden ratio described in Section 1.2.2.
现在这是对我来说毫无意义的部分 - 我认为这是一个步骤吗？ 我是否考虑使用替换模型的替换次数？ 或者我是否考虑评估的表达式数量？或者我考虑什么时候 计算算术？
我知道 space 在递归过程和迭代中是 Θ(n)（因为解释器每次递归都需要多记住一件事）和迭代 Θ(1)（作为解释器x 的一些值并继续。）我不明白斐波那契计算（树递归）如何采用 Θ(n)。
我也不知道前面的n和步数有什么关系
我的问题
下面是我所有关于增长顺序的问题列表：
算法中n的确切值是什么？
R(n)会发生什么？ （当然假设它是一个函数） n divide/multiply 是一个值吗？
我认为一个步骤是什么？
如何计算步骤的增长顺序和 space。
简而言之：
什么是增长阶数，如何计算它？
你问的是一个很长的话题。我会尽量简短地回答。然而，这是一个基本的计算机科学概念，在任何算法书籍的开头，您都会找到有关增长顺序的章节（又名 Big-O、Big-Omega 和 Big-theta 符号） .如果您有兴趣，我强烈推荐这本书：https://www.amazon.ca/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844
为了回答您的问题，科学家们无法比较他们的代码，因为原子操作在不同的机器上需要不同的时间。有很多因素会影响代码在机器上的 运行 时间，例如 OS 负载、OS 调度、在 CPU 上实现的原子操作等。因此他们提出了具有增长顺序的理论定义。
有一件事肯定会影响 运行 时间，那就是代码输入的大小，通常由 n 指出。由于 n 可能非常大，这些符号也称为渐近符号。所以，当我们谈论增长顺序时，我们假设 n 是任意大的（我们不关心小的输入大小）。简单地说，增长顺序是您的程序执行的原子步骤数（也称为基本步骤）。什么是原子？任何需要 1 或 2 或常数 CPU 操作的操作（常数，我的意思是它不依赖于 n，输入大小）。让我举一个例子。
此代码：
c = a + b
有一个原子步骤，它有求和和赋值。 另一个例子：
for i in 1..n:
print(i)
此代码有一个原子步骤 print(i) 并重复 n 次（令 n 为输入大小）。所以我们说这个程序有n个原子操作（即它的增长顺序是O(n)）。
那么，到目前为止，我希望您了解什么是原子操作以及什么是增长顺序（原子步数）。然而，通常情况下，计算增长顺序并不容易，涉及到大量的数学运算。例如，此代码：
for i in 1..n:
for j in i..n:
print(i+j)
在这段代码中，由于 j 依赖于 i，我们将进行 n + (n-1) + ... + 1 = n*(n+1)/2 原子操作。如果您计算该公式，它是 n^2 + ...。由于 n^2 在结果中有最大的指数，我们只关心那个项。在非常大的输入尺寸中，该项占主导地位，我们称其增长顺序为 O(n^2)（我知道缺少很多细节）。
因此，当我们说程序 A 的增长顺序为 O(n) 并且程序 B 的增长顺序为 O(n^2) 时，我们可以肯定，对于较大的输入大小，程序 B 会慢得多比程序 A（我们终于可以在机器上比较没有 运行 的代码）。
所以总而言之，增长的顺序是当输入大小非常大时原子操作的数量，我们不关心小操作，我们只关心最大的操作块。
我在这里的话可能会冒犯科学家和工程师。致我的科学家朋友们：当我在这里解释增长顺序时，我在数学上并不准确（如果您关心确切的数学定义，请阅读我提到的那本书）。致我的工程师朋友：是的，科学家在计算时忽略的那些小步骤 Big-o 实际上在实践中很重要，但科学家需要简化以建立基础，然后再讨论细节。
如果您想编写有效的代码，您必须了解算法的增长顺序。互联网上有很多关于这个主题的优秀资源，有些在数学上比其他的更准确，但这是我自己在数学上不准确的解释：
假设您有一些数据，例如来自数据库的 100 行，您想要处理它。现在，您实际上可以用这些数据做什么？
也许您只想打印第一行。这有多难？好吧，不是很难。你只需要一个操作就可以打印（first_row）。如果你有 1000 行，你仍然可以只用一个操作打印第一行，这种情况意味着无论你处理多少数据，它仍然会花费你相同（恒定）的时间，O(1).
然后我们有另一个非常重要的增长顺序O(log(n))。这对于在排序数据中搜索的算法来说是典型的。如果您有 100 行已排序的名称，并且您正在寻找某个名称，则只需要进行几次比较。通过每次比较，您将数据切成两半，并在 6 次操作中找到最坏情况下的名称。如果您正在查看 1000 个排序的行，则大约需要 9-10 次比较。这在大数据搜索中非常有效，您不必担心在排序数据的大数据集中搜索。总会很快的。
现在，如果您想打印所有数据，则必须在每一行上调用 print。对于 100 行，您必须执行 100 次操作，对于 1000 行，您必须执行 1000 次操作。这意味着您需要的工作量与您正在处理的数据量成正比。这将是 O(n).
O(n*n) 是您尝试在数据中查找重复行的示例。为此，您需要将每一行与其他每一行进行比较。所以你必须对 100 行进行 10000 次比较，对 1000 行进行 1000000 次比较！正如您在本例中看到的那样，所需的操作数量开始快速增长，并且这种增长可能会限制您在现代计算机上几秒钟内可以处理的数据量（您通常想要的）。这就是为什么当您看到两个 for 循环相互结合时，您必须开始小心。这也称为多项式增长。
O(e^n) 是指数增长，而且增长非常非常非常...非常快。考虑这样一种情况，您有 100 行随机数。如果您要找到总和为 50 的这些数字的所有子集，则需要大约 1267650600228229401496703205376 操作。对于 1000 行，它将是一个包含 300 个零的数字。对于作为程序员的您来说，这意味着如果您尝试像这样处理 1000 个数字，您将永远得不到结果。
O(n!) 是一个阶乘复杂度，它增长得更快，你不会用这种算法处理任何大数据集。一个典型的例子是使用 brute-force 搜索解决旅行商问题。这意味着如果有 100 行包含 100 个城市并且您想知道访问它们的顺序是什么，那么您将采用最短的路径来计算每种可能的旅行组合的距离并且它将意味着用 157 个零执行许多操作，对于 1000 个城市，该数字将有数千个零。这是一个你无法想象的疯狂数字。考虑一下宇宙中大约有 10^78 到 10^82 个原子！换句话说，您可以在计算机上针对几个城市优化销售员的路径。
您应该能够根据增长的速度对增长的顺序进行排序。将其绘制成图形并在编写某些算法时以及何时发现自己时始终考虑这幅图会很有帮助将一个循环放入另一个循环。