page70.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 109 行 · 第 1/2 页
HTML
109 行
<HTML>
<HEAD>
<TITLE>Asymptotic Analysis of Algorithms</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="tex2html2759" HREF="page71.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page71.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="tex2html2757" HREF="page56.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page56.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="tex2html2751" HREF="page69.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page69.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="tex2html2761" 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="tex2html2762" 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>
<H1><A NAME="SECTION004400000000000000000">Asymptotic Analysis of Algorithms</A></H1>
<P>
The previous chapter presents a detailed model of the computer
which involves a number of different timing parameters-- <IMG WIDTH=33 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58177" SRC="img7.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img7.gif" >, <IMG WIDTH=33 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58179" SRC="img8.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img8.gif" >, <IMG WIDTH=16 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline58189" SRC="img10.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img10.gif" >, <IMG WIDTH=15 HEIGHT=11 ALIGN=MIDDLE ALT="tex2html_wrap_inline58191" SRC="img11.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img11.gif" >, <IMG WIDTH=15 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58193" SRC="img12.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img12.gif" >, <IMG WIDTH=15 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58195" SRC="img13.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img13.gif" >,
<IMG WIDTH=15 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58197" SRC="img14.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img14.gif" >, <IMG WIDTH=26 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58201" SRC="img16.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img16.gif" >, <IMG WIDTH=42 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58203" SRC="img17.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img17.gif" >, <IMG WIDTH=23 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58579" SRC="img128.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img128.gif" >, <IMG WIDTH=41 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58581" SRC="img129.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img129.gif" >, and <IMG WIDTH=19 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58237" SRC="img31.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img31.gif" >.
We show that keeping track of the details is messy and tiresome.
So we simplify the model by measuring time in clock cycles,
and by assuming that each of the parameters is equal to one cycle.
Nevertheless, keeping track of and carefully counting all the cycles
is still a tedious task.
<P>
In this chapter we introduce the notion of asymptotic bounds,
principally big oh, and examine the properties of such bounds.
As it turns out, the rules for computing and manipulating big oh expressions
greatly simplify the analysis of the running time of a program
when all we are interested in is its asymptotic behavior.
<P>
For example,
consider the analysis of the running time of Program <A HREF="page70.html#proghorner2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page70.html#proghorner2c"><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>,
which is just Program <A HREF="page39.html#proghornerc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page39.html#proghornerc"><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> again,
an algorithm to evaluate a polynomial using Horner's rule.
<P>
<P><A NAME="2161"> </A><A NAME="proghorner2c"> </A> <IMG WIDTH=575 HEIGHT=143 ALIGN=BOTTOM ALT="program1841" SRC="img443.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img443.gif" ><BR>
<STRONG>Program:</STRONG> Program <A HREF="page39.html#proghornerc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page39.html#proghornerc"><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> Again<BR>
<P>
<P>
<P><A NAME="2163"> </A>
<P>
<A NAME="tblhorner2c"> </A>
<DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=4 BORDER FRAME=HSIDES RULES=GROUPS>
<COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
statement </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> detailed model </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> simple </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> big oh</TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> model </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=134 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58239" SRC="img32.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img32.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
4a </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=132 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline58255" SRC="img37.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img37.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
4b </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=159 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58219" SRC="img23.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img23.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3<I>n</I>+3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
4c </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=174 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58259" SRC="img38.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img38.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4<I>n</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=251 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline58261" SRC="img39.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img39.gif" >
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?