📄 page75.html

📁 wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq
💻 HTML
📖 第 1 页 / 共 2 页
字号:
12 下一页
<HTML>
<HEAD>
<TITLE>Reality Check</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="tex2html2825" HREF="page76.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page76.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="tex2html2823" HREF="page70.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page70.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="tex2html2817" HREF="page74.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page74.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="tex2html2827" 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="tex2html2828" 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="SECTION004450000000000000000">Reality Check</A></H2>
<P>
``Asymptotic analysis is nice in theory,'' you say,
``but of what practical value is it when I don't know what <I>c</I> and  <IMG WIDTH=16 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59043" SRC="img238.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img238.gif"  > are?''
Fallacies&nbsp;<A HREF="page64.html#fallacyiii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page64.html#fallacyiii"><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&nbsp;<A HREF="page64.html#fallacyiv" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page64.html#fallacyiv"><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> showed us that if we have two programs, <I>A</I> and <I>B</I>,
that solve a given problem,
whose running times are  <IMG WIDTH=81 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline60637" SRC="img518.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img518.gif"  > and  <IMG WIDTH=83 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline60639" SRC="img519.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img519.gif"  > say,
we cannot conclude in general that we should use algorithm <I>A</I>
rather than algorithm <I>B</I> to solve a particular instance of the problem.
Even if the bounds are both known to be tight,
we still don't have enough information.
What we do know for sure is that <em>eventually</em>,
for large enough <I>n</I>, program <I>A</I> is the better choice.
<P>
In practice we need not be so conservative.
It is almost always the right choice to select program <I>A</I>.
To see why this is the case,
consider the times shown in Table&nbsp;<A HREF="page75.html#tblreality" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page75.html#tblreality"><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>.
This table shows the running times computed for a very conservative scenario.
We assume that the constant of proportionality, <I>c</I>,
is one cycle of a 100&nbsp;MHz clock.
This table shows the running times we can expect
even if only one instruction is done for each element of the input.
<P>
<P><A NAME="2425">&#160;</A>
<P>
    <A NAME="tblreality">&#160;</A>
    <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=5 BORDER FRAME=HSIDES RULES=GROUPS>
12 下一页
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -