计算机英语(第三版) 3-3.4作者：刘兆毓、郑家农(普通高等教育“十一五”国家级规划教材).pptVIP

* PART Ⅱ COMPUTER SOFTWARE CHAPTER 3 MATHEMATIC FUNDAMENTALS 3.4 ALGORITHM AND ITS MEASURES chapter 3-3.4 Main point ● Goal and procedure of algorithmic analysis ● Definition features of algorithm ● Criteria of evaluating an algorithm * Main point 3.4 ALGORITHM AND ITS MEASURES In practical terms,a goal of algorithmic analysis is “to obtain sufficient understanding about the relative merits of complicated algorithms to be able to provide useful advice to someone undertaking an actual computation” Gentleman, 1973 ［1］. In broader interpretation, however, algorithmic analysis includes the study of all aspects of performance in computational problem solving, from the preliminary formulation, through the programming stages, to the final task of interpreting the results obtained［2］. *?1 We would also like to prove lower bounds on the computation time of various classes of algorithms. In order to show that there is no algorithm to perform a given task in less than a certain amount of time, we need a precise definition of what constitutes an algorithm. First, then, what is an algorithm? ?1 ● Describe the procedure of an algorithmic analysis simply 目的状语从句 宾语从句 定语从句 A procedure consisting of a finite set of unambiguous rules which specify a finite sequence of operations that provides the solution to a problem, or to a specific class of problems, is called an algorithm［3］. Several important features of this definition must now be emphasized. First, each step of an algorithm must be unambiguous and precisely defined. The actions to be carried out must be rigorously specified for each case. 定语从句 同位语从句 Secondly, an algorithm must always arrive at a problem solution after a finite number of steps. Indeed, the general restriction of finiteness is not sufficient in practice, as the number of steps needed to solve a specific problem, although finite, may be too large for practicable computation. A useful algorithm must require not only a finite number of steps