📄 page36.html
字号:
<HTML><HEAD><TITLE>Algorithm Analysis</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html1612" HREF="page37.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1610" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1604" HREF="page35.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1614" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION002000000000000000000">Algorithm Analysis</A></H1><P><A NAME="chapmodel"> </A><P>What is an algorithm and why do we want to analyze one?An algorithm is``a...step-by-step procedure for accomplishing some end.''[<A HREF="page610.html#gage">10</A>]An algorithm can be given in many ways.For example, it can be written down in English(or French, or any other ``natural'' language).However, we are interested in algorithms which have been preciselyspecified using an appropriate mathematical formalism--such as a programming language.<P>Given such an expression of an algorithm,what can we do with it?Well, obviously we can run the program and observe its behavior.This is not likely to be very useful or informative in the general case.If we run a particular program on a particular computer with a particularset of inputs,then all know is the behavior of the program in a single instance.Such knowledge is anecdotal andwe must be careful when drawing conclusions based upon anecdotal evidence.<P>In order to learn more about an algorithm,we can ``analyze'' it.By this we mean to study the specification of the algorithmand to draw conclusions about how the implementation of that algorithm--the program--will perform in general.But what can we analyze? We can<P><UL><LI> determine the running time of a program as a function of its inputs;<LI> determine the total or maximum memory space needed for program data;<LI> determine the total size of the program code;<LI> determine whether the program correctly computes the desired result;<LI> determine the complexity of the program--e.g., how easy is it to read, understand, and modify; and,<LI> determine the robustness of the program--e.g., how well does it deal with unexpected or erroneous inputs?</UL><P>In this text, we are concerned primarily with the running time.We also consider the memory space needed to execute the program.There are many factors that affect the running time of a program.Among these are the algorithm itself,the input data, and the computer system used to run the program.The performance of a computer is determined by<P><UL><LI> the hardware: <UL><LI> processor used (type and speed),<LI> memory available (cache and RAM), and<LI> disk available; </UL><LI> the programming language in which the algorithm is specified;<LI> the language compiler/interpreter used; and<LI> the computer operating system software.</UL><P>A detailed analysis of the performance of a programwhich takes all of these factors into accountis a very difficult and time-consuming undertaking.Furthermore, such an analysis is not likely to have lasting significance.The rapid pace of change in the underlying technologiesmeans that results of such analyses are not likely to beapplicable to the next generation of hardware and software.<P>In order to overcome this shortcoming,we devise a ``model'' of the behavior of a computerwith the goals of simplifying the analysiswhile still producing meaningful results.The next section introduces the first in a series of such models.<P><BR> <HR><UL> <LI> <A NAME="tex2html1615" HREF="page37.html#SECTION002100000000000000000">A Detailed Model of the Computer</A><LI> <A NAME="tex2html1616" HREF="page49.html#SECTION002200000000000000000">A Simplified Model of the Computer</A><LI> <A NAME="tex2html1617" HREF="page56.html#SECTION002300000000000000000">Exercises</A><LI> <A NAME="tex2html1618" HREF="page57.html#SECTION002400000000000000000">Projects</A></UL><HR><A NAME="tex2html1612" HREF="page37.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1610" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1604" HREF="page35.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1614" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -