算法设计技巧与分析.pptVIP

《算法设计技巧与分析》

第1章算法分析基本概念

Chapter1BasicConceptsinAlgorithmicAnalysis

•1.1Introduction

•l.2HistoricalBackground

•1.3BinarySearch

•1.3.1Analysisofthebinarysearchalgorithm

•1.4MergingTwoSortedLists

•1.5SelectinnSort

•1.6InsertionSort

•1.7Bottom-UpMergeSorting

•1.7.1Analysisofbottom-upmergesorting

•

2024-12-20华南师范大学计算机学院2

Chapter1BasicConceptsinAlgorithmicAnalysis

•1.8TimeComplexity

•1.8.1Orderofgrowth

•1.8.2TheO-notation

•1.8.3Thefl-notation

•l.8.4Thee-notation

•1.8.5MamPles

•1.8.6Complekityclassesandtheo-notation

•1.9SpaceComplexity

•1.10OptimalAlgorithms

2024-12-20华南师范大学计算机学院3

1.1引言

ØDonaldE.Knuth:计算机科学就是算法的

研究.

Ø每个领域:依赖有效算法设计

Ø运行时间:由例子到理论

Ø时间是衡量算法有效性的最好测度

Ø算法的几个方面：

Ø输入

Ø有限指令集

Ø输出(存在?Y/N)

2024-12-20华南师范大学计算机学院4

算法和程序关系

2024-12-20华南师范大学计算机学院5

程序(Program)

•程序是算法用某种程序设计语言的具体实现。

•程序可以不满足算法的有限性的性质。

u例如操作系统，是一个在无限循环中执行的程序，因而不

是一个算法。

u操作系统的各种任务可看成是单独的问题，每一个问题由

操作系统中的一个子程序通过特定的算法来实现。该子程

序得到输出结果后便终止。

2024-12-20华南师范大学计算机学院6

算法具有五个重要的特征

Ø有穷性：算法必须执行有限步之后结束；

Ø确切性：算法的每一步必须有确切的定义；

Ø输入：算法有0个或多个输入，以刻画运

算对象的初始情况；

Ø输出：算法有一个或多个输出，以反映对

输入数据加工后的结果。没有输出的算法

是毫无意义的；

Ø可行性：算法原则上能够精确地运行，而

且人们用笔和纸做有限次运算后即可完成。

2024-12-20华南师范大学计算机学院7

1.2历史背景

•20世纪,30年代能否用有效的过程来求解问题受到关注

–问题分类为:可解、不可解（存在有效过程来求解问题）

–计算