The previous examples illustrate that processes can differ considerably in the
rates at which they consume computational resources. One convenient way to
describe this difference is to use the notion of
order of growth to
obtain a gross measure of the resources required by a process as the inputs
become larger.
前面的例子说明，计算过程在消耗计算资源的速率上可能差异悬殊。描述这种差异的一种便捷方式，是使用增长的阶 (order of growth) 的概念，以此粗略衡量随着输入规模增大，一个计算过程所需资源的量。
Let n be a parameter that measures the size of the problem, and let
R
(
n
) be the amount of resources the process requires for a problem of
size n. 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. For
matrix multiplication we might take n to be the number of rows in the
matrices. In general there are a number of properties of the problem with
respect to which it will be desirable to analyze a given process. Similarly,
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.
设 n 为衡量问题规模的参数，R(n) 为该计算过程处理规模为 n 的问题时所需的资源量。在前面的例子中，我们取 n 为待计算函数的参数值，但也可以有其他选择。例如，若目标是计算某数的平方根近似值，我们可以取 n 为所要求的精度位数；对于矩阵乘法，可以取 n 为矩阵的行数。一般而言，对于一个计算过程，可以从问题的多种属性着手进行分析。类似地，R(n) 可以衡量所用内部存储寄存器的数目、所执行的基本机器操作数，等等。在每次只执行固定数量操作的计算机上，所需时间将正比于所执行的基本机器操作数。
We say that R
(
n
) has order of growth Θ
(
f
(
n
)
), written
R
(
n
)
我们称 R(n) 的增长阶为 Θ(f(n))，记作 R(n)
=
Θ
(
f
(
n
)
) (pronounced “theta of
f
(
n
)”), if there are positive constants k
1 and k
2
independent of n such that k
1
Θ(f(n))（读作「f(n) 的 theta」），若存在与 n 无关的正常数 k₁ 和 k₂，使得 k₁
f
(
n
)
f(n)
≤
R
(
n
)
R(n)
≤
k
2
k₂
f
(
n
)
for any sufficiently large value of n. (In other words, for large n,
the value R
(
n
) is sandwiched between k
1
f(n)
对所有足够大的 n 成立。（换言之，对于足够大的 n，R(n) 的值被夹在 k₁
f
(
n
) and
k
2
f(n) 与 k₂
f
(
n
).)
f(n) 之间。）
For instance, with the linear recursive process for computing factorial
described in 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 Θ
(
例如，对于 1.2.1 节中计算阶乘的线性递归型计算过程，步骤数与输入 n 成正比，因此该计算过程所需步骤数的增长阶为 Θ(n)。我们也看到，所需空间的增长阶同样为 Θ(n)。对于迭代型阶乘，步骤数仍为 Θ(n)，但空间为 Θ(1)——即常数。树形递归的斐波那契计算所需步骤数为 Θ(
φ
n
)
steps and space Θ
(
n
), where φ is the golden ratio
described in 1.2.2.
）步，空间为 Θ
(
n
)，其中 φ 是 1.2.2 节中描述的黄金比例。
Orders of growth provide only a crude description of the behavior of a process.
For example, a process requiring n
2 steps and a process requiring
1000
增长的阶只是对一个计算过程行为的粗略描述。例如，需要 n
2 步的计算过程与需要 1000
n
2 steps and a process requiring 3
n
2 步的计算过程以及需要 3
n
2
+
10
n
+
17 steps all
have Θ
(
+ 17 步的计算过程，其增长的阶均为 Θ
(
n
2
) order of growth. On the other hand, order of growth
provides a useful indication of how we may expect the behavior of the process
to change as we change the size of the problem. For a Θ
(
n
)
(linear) process, doubling the size will roughly double the amount of resources
used. For an exponential process, each increment in problem size will multiply
the resource utilization by a constant factor. In the remainder of
1.2 we will examine two algorithms whose order of growth is logarithmic,
so that doubling the problem size increases the resource requirement by a
constant amount.
）。但从另一方面来看，增长的阶能够有效地揭示：当问题规模改变时，计算过程的行为将如何随之变化。对于一个 Θ
(
n
)（线性）计算过程而言，将问题规模翻倍，所耗用的资源量大约也翻倍。对于指数型计算过程，每增加一个单位的问题规模，资源消耗量就会乘以一个常数因子。在 1.2 节的余下部分，我们将考察两个增长阶为对数的算法——对于这类算法，问题规模翻倍只会使资源需求增加一个常数量。