200分高分悬赏急用英译汉(明天早上之前要)
Figure3.1(a)givesanintuitivepictureoffunctionsf(n)andg(n),wherewehavethatf(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.
要手译,不要机译.译得好再追加50分,明天早上给分. 展开
Θ(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.
要手译,不要机译.译得好再追加50分,明天早上给分. 展开
6个回答
展开全部
连同其他俩问题
---------------
Θ-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.
---------------
Θ-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.
本回答由提问者推荐
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
展开全部
图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 :图形实例的θ, O和252Ω. 在每一部分的价值为N0证明是可能的最低值; 任何更大的价值也会工作. (一)θ-五线谱式的功能在不断的因素. 我们写利用F ( n ) =θ度( g ( n ) )中,若存在常数积极为N0 , C1值, 和C2等,以权n0时, 价值f ( n )的始终是介于法兰( n )和全身( n )的包容性. (二) O型谱给出的一个上界函数在一个常数因子
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
展开全部
图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）Θ限制了一个和常数有关的函数。如果存在常数n0, c1,和c2 ，当 n ≥ n0时，c1g(n)≤f(n)≤c2g(n)，那么，记作 f(n) = Θ(g(n))。（b）符号O表示了一个与常数有关的函数的上界。
图3.1：Θ, O,和Ω的图例。在每一部分，n0的值表示可能取得的最小值；任何比它大的值都可以。（a）Θ限制了一个和常数有关的函数。如果存在常数n0, c1,和c2 ，当 n ≥ n0时，c1g(n)≤f(n)≤c2g(n)，那么，记作 f(n) = Θ(g(n))。（b）符号O表示了一个与常数有关的函数的上界。
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
展开全部
数字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.1:Θ，O，并且Ω标志的图解的例子。
在每部分，n0的价值
出现是最小的可能的价值;
任何更伟大的价值将也工作。
(a)Θ-标志
界限到在内经常的因素的函数。
我们给f (n) =写Θ(g (n))如果存在着积极
常数n0，c1，并且c2这那在n0右面，f (n)的价值总是躺在c1g (n)之间
并且包含的c2g (n)。
为函数(b)O标志给上面的界限到在常数以内
Θ(g (n))。
为在n0右面的n的所有的值，在左右c1g (n)并且在f (n)的值躺或
在c2g (n)下面。
换句话说,为所有的n≥n0，函数f (n)等于g (n)到在以内一
经常的因素。
我们说为f (n)g (n)是渐近地紧密的界限。
数字3.1:Θ，O，并且Ω标志的图解的例子。
在每部分，n0的价值
出现是最小的可能的价值;
任何更伟大的价值将也工作。
(a)Θ-标志
界限到在内经常的因素的函数。
我们给f (n) =写Θ(g (n))如果存在着积极
常数n0，c1，并且c2这那在n0右面，f (n)的价值总是躺在c1g (n)之间
并且包含的c2g (n)。
为函数(b)O标志给上面的界限到在常数以内
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
展开全部
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时, 价
值f ( n )的谎言或以上法兰( N ) ,并且在或低于照射(氮) . 换言
之,对一切n≥n0时,函数f ( n )是平等的G ( n )为一常数因子. 我
们说有g ( N )是一个渐近紧约束为f ( n )的. 图3.1 :图形实例的
θ, O和252Ω. 在每一部分的价值为N0证明是可能的最低值; 任何更
大的价值也会工作. (一)θ-五线谱式的功能在不断的因素. 我们写
利用F ( n ) =θ度( g ( n ) )中,若存在常数积极为N0 , C1值, 和
C2等,以权n0时, 价值f ( n )的始终是介于法兰( n )和全身( n )
的包容性. (二) O型谱给出的一个上界函数在一个常数因子
Θ(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时, 价
值f ( n )的谎言或以上法兰( N ) ,并且在或低于照射(氮) . 换言
之,对一切n≥n0时,函数f ( n )是平等的G ( n )为一常数因子. 我
们说有g ( N )是一个渐近紧约束为f ( n )的. 图3.1 :图形实例的
θ, O和252Ω. 在每一部分的价值为N0证明是可能的最低值; 任何更
大的价值也会工作. (一)θ-五线谱式的功能在不断的因素. 我们写
利用F ( n ) =θ度( g ( n ) )中,若存在常数积极为N0 , C1值, 和
C2等,以权n0时, 价值f ( n )的始终是介于法兰( n )和全身( n )
的包容性. (二) O型谱给出的一个上界函数在一个常数因子
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
展开全部
图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, 和? 记法。在各部份, n0 的价值 被显示极小的可能的价值; 任一更加了不起的价值并且会运作。(a)? 记法 跳起一个作用对在恒定的因素之内。我们写f(n) =?(g(n)) 如果那里存在正面 常数n0 、c1, 和c2 这样, 在n0 右边, f(n) 的价值总放在c1g(n) 之间 并且c2g(n) 包含。(b) O 记法给一个最高界面为作用内常数 因素。
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
更多回答（4）
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
