200分高分悬赏急用英译汉(明天早上之前要)

连同其他俩问题
---------------
Θ-notation
In Chapter 2, we found that the worst-case running time of insertion sort is T (n) = Θ(n2). Let
us define what this notation means. For a given function g(n), we denote by Θ(g(n)) the set of
functions
Θ(g(n)) = {f(n) : there exist positive constants c1, c2, and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)
for all n ≥ n0}.[1]
A function f(n) belongs to the set Θ(g(n)) if there exist positive constants c1 and c2 such that it
can be "sandwiched" between c1g(n) and c2g(n), for sufficiently large n. Because Θ(g(n)) is a
set, we could write "f(n)  Θ(g(n))" to indicate that f(n) is a member of Θ(g(n)). Instead, we
will usually write "f(n) = Θ(g(n))" to express the same notion. This abuse of equality to denote
set membership may at first appear confusing, but we shall see later in this section that it has
advantages.
θ-符号
在第2章中,我们看到的最坏的运行排序是T(n)=θ(n2) . 让我们确定这个公式代表了什么. 对于给定函数G(n),我们定义θ(g(n))为g(n)的函数集.
Θ(g(n))=｛f(n): 存在正常数C1、C2和N0,当0≤c1g(n)≤f(n)≤c2g(n),其中n≥ n0} .
[1]若存在正常数C1、C2等以使之满足c1g(n)≤f(n)≤c2g(n),如果n足够大,那么函数f(n)属于函数集θ(g(n)).因为θ(g(n))是一个集合,我们可以用"f(n) θ(g(n))"来表明f(n)包含于θ(g(n)). 但是,我们通常会写"f(n)=θ(g(n))"来表达这一概念. 这种等号定义的滥用使得工作组在开始时会出现混乱, 但是,我们应当看到,在这一节梢后,它有许多优点.
Figure 3.1(a) gives an intuitive picture of functions f(n) and g(n), where we have that f(n) =
Θ(g(n)). For all values of n to the right of n0, the value of f(n) lies at or above c1g(n) and at or
below c2g(n). In other words, for all n ≥ n0, the function f(n) is equal to g(n) to within a
constant factor. We say that g(n) is an asymptotically tight bound for f(n).
Figure 3.1: Graphic examples of the Θ, O, and Ω notations. In each part, the value of n0
shown is the minimum possible value; any greater value would also work. (a) Θ-notation
bounds a function to within constant factors. We write f(n) = Θ(g(n)) if there exist positive
constants n0, c1, and c2 such that to the right of n0, the value of f(n) always lies between c1g(n)
and c2g(n) inclusive. (b) O-notation gives an upper bound for a function to within a constant
factor.
图3.1(a):给出函数f(n)和g(n)的曲线,其中,f(n)=Θ(g(n)).当n≥n0时,c1g(n)≤f(n)≤c2g(n).也就是说,当n≥n0时,f(n)等于g(n)乘以一个常数.我们说,g(n)是f(n)的同类型曲线.
图3.1：Θ, O,和Ω的图例.在每个部分,n0取最小可能值；任何比它大的值都可以.
(a)Θ限制了一个和常数有关的函数.如果存在正常数n0、c1和c2,当 n≥n0时,c1g(n)≤f(n)≤c2g(n),那么,我们记作f(n) = Θ(g(n)).
(b)符号O表示了一个与常数有关的函数的上限.
We write f(n) = O(g(n)) if there are positive constants n0 and c such that to the right of
n0, the value of f(n) always lies on or below cg(n). (c) Ω-notation gives a lower bound for a
function to within a constant factor. We write f(n) = Ω(g(n)) if there are positive constants n0
and c such that to the right of n0, the value of f(n) always lies on or above cg(n).
The definition of Θ(g(n)) requires that every member f(n)  Θ(g(n)) be asymptotically
nonnegative, that is, that f(n) be nonnegative whenever n is sufficiently large. (An
asymptotically positive function is one that is positive for all sufficiently large n.)
Consequently, the function g(n) itself must be asymptotically nonnegative, or else the set
Θ(g(n)) is empty. We shall therefore assume that every function used within Θ-notation is
asymptotically nonnegative. This assumption holds for the other asymptotic notations defined
in this chapter as well.
In Chapter 2, we introduced an informal notion of Θ-notation that amounted to throwing away
lower-order terms and ignoring the leading coefficient of the highest-order term. Let us
briefly justify this intuition by using the formal definition to show that 1/2n2 - 3n = Θ(n2). To
do so, we must determine positive constants c1, c2, and n0 such that
c1n2 ≤ 1/2n2 - 3n ≤ c2n2
for all n ≥ n0. Dividing by n2 yields
c1 ≤ 1/2 - 3/n ≤ c2.
当有正常数n0和大于n0的常数c,我们就记作 f(n) = O(g(n)) ,其中f(n)≤cg(n).

(c) Ω符号表示在给定常数范围内的函数下限.当有正常数n0和大于n0的常数c,我们记作f(n) = Ω(g(n)) ,其中f(n)≥cg(n).
Θ(g(n)) 的定义要求每一个 f(n) Θ(g(n)) 都是渐近正函数,就是说,无论n多大,f(n) 都为正的(渐近的正函数就是一个对所有足够大的n来说都为正的函数)；因此,函数 g(n) 本身必须为渐近非负函数,否则Θ(g(n)) 就是空集.因此我们应该假设Θ的所有子函数都为渐近非负函数.这种假设在这章中其他的渐近符号定义中也成立.

在第二章,我们介绍了一个非正式的符号 Θ-符号,这种符号总计丢弃低项,并且忽略高次项的首项系数.让我们简要地通过正式地定义来表示1/2n2 - 3n = Θ(n2)的方法来证明这种直觉是对的,为了这样做,我们必须规定正常数c1,c2和n0满足：
c1n2≤1/2n2-3n≤c2n2
对于所有的n ≥ n0,用n2除后,
c1≤1/2-3/n≤c2.

Figure 3.1(a) gives an intuitive picture of functions f(n) and g(n), where we have that f(n) =
Θ(g(n)). For all values of n to the right of n0, the value of f(n) lies at or above c1g(n) and at or...

图3.1(a) 给作用f(n) 和g(n) 的一张直觉的图片, 我们有那f(n) = ?(g(n)) 。为所有n 的价值在n0 右边, f(n) 的价值说谎在或在c1g(n) 之上和在或 在c2g(n) 以下。换句话说, 为所有n? n0, 作用f(n) 与g(n) 是相等的与在a 之内 恒定的因素。我们说, g(n) 是一个渐进地紧的区域为f(n) 。 图3.1: 图表例子?, O, 和? 记法...

图3.1 ( a )条给予一个直观的图像函数f ( n )的和G ( n ) ,在那里,我们有f ( n )的=θ度( G ( n )段) . 所有N值的右边n0时, 价值f ( n )的谎言或以上法兰( N ) ,并且在或低于照射(氮) . 换言之,对一切n≥n0时,函数f ( n )是平等的G ( n )为一常数因子. 我们说有g ( N )是一个渐近紧约束为f ( n )的. 图3.1 :图...

图3.1（a）给出了函数f（n）和g（n）的曲线，其中，f(n) =Θ(g(n))。当n ≥ n0时，f（n）大于等于c1g(n)，且小于等于 c2g(n)。也就是说，当n ≥ n0时，f(n)等于g(n)乘以一个常数。我们说，g(n)是渐进紧约束着f(n)的范围。
图3.1：Θ, O,和Ω的图例。在每一部分，n0的值表示可能取得的最小值；任何比它大的值都可以。（a）Θ限制了一个和常数有...

数字3.1 (a)给函数f (n)和g (n)的直观的图片,我们在此有那f (n) =
Θ(g (n))。
为在n0右面的n的所有的值，在左右c1g (n)并且在f (n)的值躺或
在c2g (n)下面。
换句话说,为所有的n≥n0，函数f (n)等于g (n)到在以内一
经常的因素。
我们说为f (n)g (n)是渐近地紧密的界限。
数字3...