《算法设计与分析》-第一章 算法引论

算法分析与设计 课程介绍 计划学时 32 8教材王晓东 算法设计与分析 北京 清华大学出版社 2003 1参考书目 美 MarkAllenWeiss 数据结构与算法分析 C语言描述 冯舜玺译 机械工业出版社 2004 1 美 EllisHorowitz SartajSahni SanguthevarRajasekaran 计算机算法 C 版 冯博琴等译 机械工业出版社 2006 1 目录 第一讲算法引论第二讲基本数据结构与常用算法第三讲递归与分治第四讲动态规划第五讲贪心算法第六讲回溯法第七讲分支限界法第八讲概率算法 NP完全性理论及算法研究和应用现状介绍 第一讲算法引论 本章主要内容1 1什么是算法1 2算法与程序的区别1 3算法的描述1 4算法的性能分析 第一讲算法引论 1 1什么是算法算法 Algorithm 一词有Algorism衍生而来 Algorism原作算术解释 来源于波斯作家AbuJa farMahammedibnMusaalKowarizmi的名字 大约825年 他写了一本关于数学的教科书 第一讲算法引论 1 1什么是算法算法 Algorithm 是完成特定任务的有限指令集 它具有五个特性 1 输入 由外部提供零个或多个输入量 2 输出 至少产生一个输出3 确定性 每条指令必须清晰 无歧义 4 有穷性 一个算对任何一个输入必须在执行有穷步后终止 5 可行性 每条指令必须非常基础 原则上用纸和笔就可以实现 第一讲算法引论 1 2算法和程序的区别一个计算机程序 Program 往往是指用某种计算机语言书写的一个计算过程或算法 要在计算机上执行 一个算法有多种描述方式 既可以编成程序在计算机上执行 也可以用其它的工具 笔和纸 算盘等 来执行 一个特定的算法不一定和一个程序有关系 第一讲算法引论 1 3算法的描述用自然语言表示用流程图表示 传统流程图和N S图 用伪代码表示用计算机语言表示 第一讲算法引论 1 3算法的描述 例1 有两个数a b 按大小顺序打印它们 自然语言描述 步骤1 输入a b的值 步骤2 如果a b 则先打印a 再打印b 否则 先打印b 再打印a 算法结束 用自然语言表示算法的特点 通俗易懂 但不严谨 容易产生歧义 第一讲算法引论 1 3算法的描述用流程图表示 第一讲算法引论 1 3算法的描述用N S图表示 用基本结构的组合表示算法 从而去掉了流程线 避免了随意的跳转 1973年两名美国学者提出了一种新的流程图形式 并用二人名字的第一个字母组合命名了该流程图 即N S流程图 也称盒图 三种基本结构的表示 不成立 当条件P成立时 直到条件P1成立 第一讲算法引论 1 3算法的描述用N S图表示 第一讲算法引论 1 3算法的描述用伪码表示 例2 求1X2X3X4X5 开始置p的初值为1置i的初值为1当i小于5时 执行下面的操作 使p pxi使i i 1打印p的值结束 第一讲算法引论 1 3算法的描述用类计算机语言表示 第一讲算法引论 1 4算法的性能分析几个概念 问题的规模n SizeofProblem 又称为输入规模 inputsize 是输入量大小的一个测度 时间复杂度T n 算法运行所需的计算时间 TimeComplexity空间复杂度S n 算法运行所需的存储空间 SpaceComplexity 第一讲算法引论 1 4算法的性能分析算法的性能评价大致分为两类 1 先验估计 2 后验测试 分别称为性能分析和性能度量 第一讲算法引论 1 4算法的性能分析渐近符号 O o设f n 和g n 是定义在正数集上的非负函数 O bigO f n O g n 读作f n 是g n 的大O 当且仅当存在两个正常数C和n0 使得对所有的n n0 有f n C g n omega f n g n 读作f n 是g n 的omega 当且仅当存在两个正常数C和n0 使得对所有的n n0 有f n C g n 第一讲算法引论 1 4算法的性能分析 theta f n g n 读作f n 是g n 的theta 当且仅当存在正常数C1 C2和n0 使得对所有的n n0 有C1 g n f n C2 g n o smallo f n o g n 读作