算法设计技巧与分析

Contents

PART 1 Basic Concepts and Introduction to Algorithms

Chapter 1 Basic Concepts in Algorithmic Analysis

1.1 Introduction

1.2 Historical Background

1.3 Binary Search

1.3.1 Analysis of the binary search algorithm

1.4 Merging Two Sorted Lists

1.5 Selection Sort

1.6 Insertion Sort

1.7 BottomJ.Jp Merge Sorting

1.7.1 Analysis of bottom-up merge sorting

1.8 Time Complexity

1.8.1 Order of growth

1.8.2 The O-notation

1.8.3 The Ω-notation

1.8.4 The Θ-notation

1.8.5 Examples

1.8.6 Complexity classes and the e notation

1.9 Space Complexity

1.10 optimal Algorithms

1.11 How to Estimate the Running Time of an Algorithm

1.11.1 Counting the number of iterations

1.11.2 Counting the frequency of basic operations

1.11.3 Using recurrence relations

1.12 Worst case and average case analysis

1.12.1 Worst case analysis

1.12.2 Average case analysis

1.13 Amortized Analysis

1.14 Input Size and Problem Instance

1.15 Exercises

1.16 Bibliographic Notes

Chapter 2 Mathematical Preliminaries

2.1 Sets, Relations and Functions

2.1.1 Sets

2.1.2 Relations

2.1.2.1 Equivalence relations

2.1.3 Functions

2.2 Proof Methods

2.2.1 Direct proof

2.2.2 Indirect proof

2.2.3 Proof by contradiction

2.2.4 Proof by counterexampIe

2.2.5 Mathematic induction

2.3 Logarithms

2.4 Floor and Ceiling Functions

2.5 Factorial and Binomial Coefficients

2.5.1 Factorials

2.5.2 Binomial coefficients

2.6 The Pigeonhole Principle

2.7 summations

2.7.1 Approximation of summations by integration

2.8 Recurrence Relations

2.8.1 Solution of linear homogeneous recurrences

2.8.2 Solution of inhomogeneous recurrences

2.8.3 Solution of divide-and-conquer recurrences

2.8.3.1 Expanding the recurrence

2.8.3.2 Substitution

2.8.3.3 Change of variables

2.9 Exercises

《算国外计算机科学教材系列：算法设计技巧与分析（英文版）》是国际著名算法专家李德财教授主编的系列丛书“Lecture Notes Series on Computing”中的一本。《算国外计算机科学教材系列：算法设计技巧与分析（英文版）》涵盖了绝大多数算法设计中的一般技术，在表达每一种技术时，阐述它的应用背景，注意用与其他技术比较的方法说明它的特征，并提供大量相应实际问题的例子。全书分七部分19章，从算法设计和算法分析的基本概念和方法入手，先后介绍了递归技术、分治、动态规划、贪心算法、图的遍历等技术，并且对NP完全问题进行了基本但清楚的讨论。