发帖
雷达卡
Introduction
When you design and analyze algorithms, you need to be able to describe how they operate and how to design them. You also need some mathematical tools to show that your algorithms do the right thing and do it efûciently. This part will get you started. Later parts of this book will build upon this base.
Chapter 1 provides an overview of algorithms and their place in modern com- puting systems. This chapter deûnes what an algorithm is and lists some examples. It also makes a case for considering algorithms as a technology, alongside tech- nologies such as fast hardware, graphical user interfaces, object-oriented systems, and networks.
In Chapter 2, we see our ûrst algorithms, which solve the problem of sorting a sequence of numbers. They are written in a pseudocode which, although not directly translatable to any conventional programming language, conveys the struc- ture of the algorithm clearly enough that you should be able to implement it in the language of your choice. The sorting algorithms we examine are insertion sort, which uses an incremental approach, and merge sort, which uses a recursive technique known as "divide-and-conquer". Although the time each requires increases with the value of , the rate of increase differs between the two algorithms. We determine these running times in Chapter 2, and we develop a useful "asymptotic" notation to express them.
Chapter 3 precisely deûnes asymptotic notation. We’ll use asymptotic notation to bound the growth of functions4most often, functions that describe the running time of algorithms4from above and below. The chapter starts by informally deûn- ing the most commonly used asymptotic notations and giving an example of how to apply them. It then formally deûnes ûve asymptotic notations and presents conven- tions for how to put them together. The rest of Chapter 3 is primarily a presentation of mathematical notation, more to ensure that your use of notation matches that in this book than to teach you new mathematical concepts.
Chapter 4 delves further into the divide-and-conquer method introduced in Chapter 2. It provides two additional examples of divide-and-conquer algorithms for multiplying square matrices, including Strassen’s surprising method. Chapter 4 contains methods for solving recurrences, which are useful for describing the run- ning times of recursive algorithms. In the substitution method, you guess an answer and prove it correct. Recursion trees provide one way to generate a guess. Chap- ter 4 also presents the powerful technique of the "master method", which you can often use to solve recurrences that arise from divide-and-conquer algorithms. Al- though the chapter provides a proof of a foundational theorem on which the master theorem depends, you should feel free to employ the master method without delv- ing into the proof. Chapter 4 concludes with some advanced topics.
Chapter 5 introduces probabilistic analysis and randomized algorithms. You typically use probabilistic analysis to determine the running time of an algorithm in cases in which, due to the presence of an inherent probability distribution, the running time may differ on different inputs of the same size. In some cases, you might assume that the inputs conform to a known probability distribution, so that you are averaging the running time over all possible inputs. In other cases, the probability distribution comes not from the inputs but from random choices made during the course of the algorithm. An algorithm whose behavior is determined not only by its input but by the values produced by a random-number generator is a randomized algorithm. You can use randomized algorithms to enforce a probability distribution on the inputs4thereby ensuring that no particular input always causes poor performance4or even to bound the error rate of algorithms that are allowed to produce incorrect results on a limited basis.
Appendices A–D contain other mathematical material that you will ûnd helpful as you read this book. You might have seen much of the material in the appendix chapters before having read this book (although the speciûc deûnitions and nota- tional conventions we use may differ in some cases from what you have seen in the past), and so you should think of the appendices as reference material. On the other hand, you probably have not already seen most of the material in Part I. All the chapters in Part I and the appendices are written with a tutorial üavor.
提升卡
置顶卡
沉默卡
变色卡
抢沙发
千斤顶
显身卡
京公网安备 11010802022788号
