📄 page60.html
字号:
<HTML>
<HEAD>
<TITLE>Properties of Big Oh</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html2641" HREF="page61.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page61.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html2639" HREF="page57.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page57.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html2633" HREF="page59.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page59.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html2643" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html2644" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION004130000000000000000">Properties of Big Oh</A></H2>
<P>
In this section we examine some of the mathematical properties of big oh.
In particular, suppose we know that <IMG WIDTH=118 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59227" SRC="img265.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img265.gif" > and <IMG WIDTH=117 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59229" SRC="img266.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img266.gif" >.
<UL><LI> What can we say about the asymptotic behavior of the <em>sum</em> of
<IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59231" SRC="img267.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img267.gif" > and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59233" SRC="img268.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img268.gif" >?
(Theorems <A HREF="page60.html#theoremi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremi"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> and <A HREF="page60.html#theoremii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremii"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>).<LI> What can we say about the asymptotic behavior of the
<em>product</em> of <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59231" SRC="img267.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img267.gif" > and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59233" SRC="img268.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img268.gif" >?
(Theorems <A HREF="page60.html#theoremiii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> and <A HREF="page60.html#theoremiv" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>).<LI> How are <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59231" SRC="img267.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img267.gif" > and <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59241" SRC="img269.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img269.gif" > related when
<IMG WIDTH=94 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59243" SRC="img270.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img270.gif" >?
(Theorem <A HREF="page60.html#theoremv" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremv"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>).
</UL>
<P>
The first theorem addresses the asymptotic behavior of the sum
of two functions whose asymptotic behaviors are known:
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theoremi"> </A>
If <IMG WIDTH=118 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59227" SRC="img265.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img265.gif" > and <IMG WIDTH=117 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59229" SRC="img266.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img266.gif" >,
then
<P> <IMG WIDTH=381 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath59215" SRC="img271.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img271.gif" ><P></BLOCKQUOTE>
<P>
extbfProof
By Definition <A HREF="page57.html#defnbigoh" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page57.html#defnbigoh"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>, there exist two integers, <IMG WIDTH=16 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59249" SRC="img272.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img272.gif" > and <IMG WIDTH=16 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59251" SRC="img273.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img273.gif" >
and two constants <IMG WIDTH=13 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59253" SRC="img274.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img274.gif" > and <IMG WIDTH=13 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59255" SRC="img275.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img275.gif" > such that
<IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59257" SRC="img276.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img276.gif" > for <IMG WIDTH=47 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59259" SRC="img277.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img277.gif" > and
<IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59261" SRC="img278.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img278.gif" > for <IMG WIDTH=47 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59263" SRC="img279.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img279.gif" >.
<P>
Let <IMG WIDTH=119 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59265" SRC="img280.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img280.gif" > and <IMG WIDTH=122 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59267" SRC="img281.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img281.gif" >.
Consider the sum <IMG WIDTH=91 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59269" SRC="img282.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img282.gif" > for <IMG WIDTH=46 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59075" SRC="img242.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img242.gif" >:
<P> <IMG WIDTH=500 HEIGHT=63 ALIGN=BOTTOM ALT="eqnarray1403" SRC="img283.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img283.gif" ><P>
Thus, <IMG WIDTH=259 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59273" SRC="img284.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img284.gif" >.
<P>
According to Theorem <A HREF="page60.html#theoremi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremi"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>,
if we know that functions <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59231" SRC="img267.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img267.gif" > and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59233" SRC="img268.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img268.gif" > are
<IMG WIDTH=60 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59279" SRC="img285.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img285.gif" > and <IMG WIDTH=59 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59281" SRC="img286.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img286.gif" >, respectively,
the <em>sum</em> <IMG WIDTH=91 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59269" SRC="img282.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img282.gif" > is <IMG WIDTH=146 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59285" SRC="img287.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img287.gif" >.
The meaning of <IMG WIDTH=121 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59287" SRC="img288.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img288.gif" > is this context is
the <em>function</em> <I>h</I>(<I>n</I>) where <IMG WIDTH=173 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59291" SRC="img289.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img289.gif" >
for integers all <IMG WIDTH=38 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59063" SRC="img241.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img241.gif" >.
<P>
For example, consider the functions <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59295" SRC="img290.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img290.gif" > and
<IMG WIDTH=144 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59297" SRC="img291.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img291.gif" >.
Then
<P> <IMG WIDTH=500 HEIGHT=94 ALIGN=BOTTOM ALT="eqnarray1408" SRC="img292.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img292.gif" ><P>
<P>
Theorem <A HREF="page60.html#theoremii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremii"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> helps us simplify the asymptotic analysis
of the sum of functions by allowing us to drop the <IMG WIDTH=30 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline59303" SRC="img293.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img293.gif" >
required by Theorem <A HREF="page60.html#theoremi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremi"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> in certain circumstances:
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theoremii"> </A>
If <IMG WIDTH=144 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59305" SRC="img294.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img294.gif" >
in which <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59231" SRC="img267.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img267.gif" > and <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59233" SRC="img268.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img268.gif" > are both non-negative for all integers <IMG WIDTH=38 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59063" SRC="img241.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img241.gif" >
such that <IMG WIDTH=172 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59313" SRC="img295.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img295.gif" >
for some limit <IMG WIDTH=38 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline59315" SRC="img296.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img296.gif" >,
then <IMG WIDTH=113 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59317" SRC="img297.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img297.gif" >.
</BLOCKQUOTE>
<P>
extbfProof
According to the definition of limits<A NAME=1422> </A>, the notation
<P> <IMG WIDTH=304 HEIGHT=38 ALIGN=BOTTOM ALT="displaymath59216" SRC="img298.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img298.gif" ><P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -