time-complexity - 什么是增长顺序以及如何计算它？

Question

为什么我会问这个问题

最近开始看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) 可能是执行的基本操作数，但是 执行的操作数是否因操作系统而异？作为 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.

现在这是对我来说毫无意义的部分 - 我将什么视为一个步骤？ 我是否考虑使用替换模型的替换次数？ 或者我是否考虑评估的表达式数量？或者我考虑什么时候 算术评估？

我知道在递归过程和迭代 Θ(1) 中空间是 Θ(n)(因为解释器每次递归都需要记住 1 个以上的东西)(作为解释器 x 的一些值并继续.) 我不明白 Fibonacci 计算(树递归)如何采用 Θ(n)。

我也不知道前面的 n 与步数有何关系。

我的问题

下面列出了我所有与增长顺序有关的问题:

1. 算法中哪个精确值是 n？

2. R(n) 中发生了什么？ (当然假设它是一个函数)n 是否除/乘一个值？

3. 我认为一个步骤是什么？

4. 如何计算步长和空间的增长顺序。

简而言之:

什么是增长阶数，如何计算它？

Answer 1

你问的是一个很长的话题。我会尽量简短地回答。然而，这是一个基本的计算机科学概念，在任何算法书籍的开头，您都会找到有关增长阶数(又名 Big-O、Big-Omega 和 Big-theta 符号)的章节。如果您有兴趣，我强烈推荐这本书:https://www.amazon.ca/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844

为了回答您的问题，科学家无法比较他们的代码，因为原子操作在不同机器上花费的时间不同。许多因素都会影响代码在机器上的运行时间，例如操作系统负载、操作系统调度、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 慢得多(我们终于可以在不在机器上运行代码的情况下比较代码)。

总而言之，当输入大小非常大时，增长的顺序是原子操作的数量，我们不关心小操作，我们只关心最大的操作 block 。

我在这里的话可能会冒犯科学家和工程师。致我的科学家 friend 们:当我在这里解释增长顺序时，我在数学上并不准确(如果您关心确切的数学定义，请阅读我提到的那本书)。致我的工程师 friend :是的，科学家在计算 Big-o 时忽略的那些小步骤在实践中实际上很重要，但科学家需要简化以建立基础，然后讨论细节。