【文件属性】:
文件名称:Introduction to Algorithms(算法导论)
文件大小:12.51MB
文件格式:PDF
更新时间:2016-11-24 12:26:11
算法
May 2001
Part I: Foundations
Chapter List
Chapter 1: The Role of Algorithms in Computing
Chapter 2: Getting Started
Chapter 3: Growth of Functions
Chapter 4: Recurrences
Chapter 5: Probabilistic Analysis and Randomized Algorithms
Introduction
This part will get you started in thinking about designing and analyzing algorithms. It is
intended to be a gentle introduction to how we specify algorithms, some of the design
strategies we will use throughout this book, and many of the fundamental ideas used in
algorithm analysis. Later parts of this book will build upon this base.
Chapter 1 is an overview of algorithms and their place in modern computing systems. This
chapter defines what an algorithm is and lists some examples. It also makes a case that
algorithms are a technology, just as are fast hardware, graphical user interfaces, objectoriented
systems, and networks.
In Chapter 2, we see our first algorithms, which solve the problem of sorting a sequence of n
numbers. They are written in a pseudocode which, although not directly translatable to any
conventional programming language, conveys the structure of the algorithm clearly enough
that a competent programmer can implement it in the language of his 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 n, the rate of increase differs between the two
algorithms. We determine these running times in Chapter 2, and we develop a useful notation
to express them.
Chapter 3 precisely defines this notation, which we call asymptotic notation. It starts by
defining several asymptotic notations, which we use for bounding algorithm running times
from above and/or below. The rest of Chapter 3 is primarily a presentation of mathematical
notation. Its purpose is 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. In
particular, Chapter 4 contains methods for solving recurrences, which are useful for
describing the running times of recursive algorithms. One powerful technique is the "master
method," which can be used to solve recurrences that arise from divide-and-conquer
algorithms. Much of Chapter 4 is devoted to proving the correctness of the master method,
though this proof may be skipped without harm.
网友评论
- 有关算法的经典书籍
- 有关算法的经典书籍,值得下载。