算法与结构课件第一章绪论(华北电力大学科技学院).ppt

计算机算法设计与分析,North China Electric Power University,Computer Algorithms Design & Analysis,华北电力大学计算机科学与工程系,Dept. of Computer Science&Engineering of North China Electric Power University,本课程解决哪些问题,本课程主要介绍在实践应用中行之有效的解决非数值数据处理问题的若干经典的计算机算法，以帮助学生提高运行计算机解决具体问题的能力！ 基本内容如下 1、算法简介 2、递归 3、分治法 4、动态规划法 石子合并问题 5、贪心法最少硬币个数问题 6、回溯法数字组合问题,算法学习之乐趣,1、久违的小学生成功解决应用题般的兴奋 2、难言之隐、十周根治 我已学习语言很多年，编程仍然不过关的苦恼。去玩玩数据结构和算法吧。 3、考学、升级之必经之路 数据结构和算法是各种考试的座上客 4、认清问题本质 是否对日新月异的开发工具跟得疲惫，当初对学计算机的兴趣大大降低，设计的软件是否存在一些问题，你难以快速理清它的逻辑，并给出高效的解决方案，玩算法吧！它能使你快速看清楚一些常见问题的本质，并提供你各种解决方案进行选择！也是使你区别于代码工人的方式之一。 5、计算机科学之最终武器 算法的优化与处理 6、玩网游攻关般的快感 在这里不讨论具体编程语言，只分析问题，设计算法，分析算法！当然，实践是检验真理的客观标准，C+或Java语法你得先了解，我们通过北大在线测评网站提交程序，机器判断你的算法是否正确，耗时如何，耗内存如何？去注册帐号练级吧！,1、理论上可计算 2、现实上可计算,理论上可计算-可计算性理论 提出很多合理的计算模型，（递归函数、图灵机、post系统等等）由这些模型规定哪些问题是可计算的。,现实上可计算-计算复杂性理论 这个问题涉及到算法的时间、空间复杂性等,算法主要研究的问题及其课程目的,North China Electric Power University,课程目的: 以算法设计为主，介绍算法设计的主要方法和基本思想； 并简要介绍算法分析概念 不是程序设计课，也不是数学课,第一章 算法简介, 算法的基本概念, 算法的设计与分析, 算法的复杂性,North China Electric Power University, 算法描述语言(C+)的说明,算法+数据结构=程序 (Niklaus Wirth) （Algorithms+Data Structure=Program),程序设计：为计算机处理问题编写的一组指令。,算法：处理问题的方法和策略。,数据结构：问题的数学模型。,程序设计的实质是数据的表示和数据处理,为此 应提出问题的数学模型和设计相应的算法。 数据结构是基础，算法是灵魂,1 算法的基本概念,North China Electric Power University,算法：解决问题的方法和策略，指为解决一个或 一类问题给出的一个确定的、有限长的操作序列。,算法的特性:,1. 有穷性,2. 确定性,3. 可行性,4. 有输入,5. 有输出,North China Electric Power University,算法与算法设计,问题求解(Problem Solving),算法分析的基本原则,正确性 定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。 正确性证明的内容： 方法的正确性证明算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。 程序的正确性证明证明所给出的一系列指令确实做了所要求的工作。 程序正确性证明的方法： 大型程序的正确性证明可以将它分解为小的相互独立的互不相交的模块，分别验证。 小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。,算法分析的基本原则,工作量时间复杂性分析 计量工作量的标准: 对于给定问题，该算法所执行的基本运算的次数。 基本运算的选择：根据问题选择适当的基本运算。,算法分析的基本原则,占用空间空间复杂性分析 两种占用： 存储程序和输入数据的空间 存储中间结果或操作单元所占用空间额外空间 影响空间的主要因素： 存储程序的空间一般是常数(和输入规模无关) 输入数据空间为输入规模O(n) 空间复杂性考虑的是额外空间的大小 如果额外空间相对于输入规模是常数，称为原地工作的算法。,2 算法的复杂性,算法的复杂性,复杂性：指实现或运行某一算法所需资源的多少。,时间复杂性,空间复杂性,人工复杂性(指编程、调试等所需的人工),算法的复杂性：C=F(N,I) N：问题的规模 I：算法的输入,时间复杂性：T=T(N,I) 空间复杂性：S=S(N,I),North China Electric Power University,根据T(N,I)的概念，因为统计时间很复杂，我们一般规定一种元运算，看这种元运算在算法中的运行次数。,显然，我们不能对规模N的每一种合法的输入I都去算一次复杂度， 只能在规模为N的某些或某类有代表性的合法输入中统计， 来评价其复杂性。 一般有最坏情况下的时间复杂性W(N)、平均情况下的时间复杂性 A(N),最好情况下的时间复杂性我们一般不讨论，意义不大。 算法求解输入规模为N的实例所需要的最坏时间和平均时间分别 称为最坏情况下和平均情况下的时间复杂性。平均情况下的时间 复杂性一般需要知道算法输入的分布情况，也就是算法输入的 概率分布状况。,North China Electric Power University,最好，最坏和平均情形时间复杂度,当长度相同的不同输入有不同的计算时间时，时间复杂度分析分别考虑三种情形：即最好，最坏和平均. 当应用对计算时间有严格要求时，应做最坏情形分析-upper bound. 最好情形分析给出一个算法的计算时间的下界，用来否定一个算法.,复杂性表示： 针对问题选择基本运算 基本运算的次数表示为输入规模的函数，称为复杂性函数 下面看一个具体实例,North China Electric Power University,搜索问题： 输入：数组L，元素数为n,数X 输出：j. 若X在L中，j是X首次出现的下标 否则 j=0 算法 ：顺序搜索 假设X在L中出现的概率为p,X在L中不同位置是等概率分布，则 W(n)=n A(n)=p(n+1)/2+(1-p)n,操作计数,Program 1.31 Finding the largest elements,如果包含其他operations，则时间复杂度某常数*t(n)。,实例特征 : n , operation: comparison t(n)=n-1 且不可少于n-1,例题2.7 Max Element,Polynomial Evaluation,Program 2.3 A function to evaluate a polynomial,实例特征 : n , operation: multiplication, t(n)=2n,算法的渐近复杂性：,North China Electric Power University,的定义： 如果存在正的常数C和自然数N0,使得当NN0时,有f(N)Cg(N),则称函数f(N)当N充分大时有下界；且g(N)是它的一个下界，记为f(N)=(g(N)。不低于g(N)的阶,North China Electric Power University,的定义： 定义f(N)=(g(N),当且仅当f(N)=O(g(N)且f(N)= (g(N) 。这时，称f(N)和g(N)同阶。 o的定义： 如果对于任意给定的0,都存在正整数NN0，使得当NN0时,有f(N)/g(N),则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g(N)。F(N)的阶低于g(N)的阶 例如：4NLog N+7=o(3N2+4NLog N+7) O(1)表示常数函数,2.4渐近分析(续),渐近分析-随n的增加T(n)的增长率,设A1,A2,A6是求解同一问题的6个不同的算法，它们的渐近时间复杂性分别为N，NlogN，N 2，N 3，2N，N!。让这六种算法各在C1和C2两台计算机上运行，并设计算机C2的计算速度是计算机C1的10倍。在可接受的一段时间内，设在C1上算法Ai可能求解的问题的规模为N1i，而在C2上可能求解的问题的规模为N2i，那么，我们就应该有Ti(N2i)=10Ti(N1i)，其中Ti(N)是算法Ai渐近的时间复杂性，i=1,2,6。分别解出N2i和N1i的关系，可列成下表：,多项式时间算法和指数时间算法：,算法与渐近时间复杂性的关系,另外，从解决问题的规模来分析，当问题规模变大时，指数时间复杂度所用时间爆炸性增长，比如为2n的时间复杂度函数，当n为10时，可能只需要0.001秒，当n为60时，需要366世纪，这个时间我们不能接受。,从上面可知，多项式时间可以求解的问题和难解的问题是有区别的。 我们把不存在多项式时间可解得问题称为难解的问题。 实际上可以计算的问题就是存在多项式时间算法的问题。,多项式时间算法,如果一算法的最坏情形时间复杂度t(n)=O(nk),则称该算法为多项式复杂度的算法或有多项式界的算法. 如果一算法的最坏情形时间复杂度t(n)不能用多项式限界,则称该算法为指数复杂度的算法。这类算法可认为计算上不可行的算法。,从上面可知，多项式时间可以求解的问题和难解的问题是有区别的。 我们把不存在多项式时间可解得问题称为难解的问题。 实际上可以计算的问题就是存在多项式时间算法的问题。,NP-hard 问题,如果一个问题有多项式界的算法称该问题属于多项式类P 有很多实际上有意义的问题找不到有多项式界的算法称这些问题是NP-hard问题,即问题本身难. 上述难问题只能通过近似算法或启发式算法求解.,4 算法描述语言C+的简介,1.变量、指针和引用,1)变量 变量：是程序设计语言对存储单元的抽象，具有以下的属性： 变量名：用于标识变量的符号。 地址：变量所占据的存储单元的地址。 大小：该变量所占据的存储空间的数量(以字节数来衡量)。 类型：变量所取的值域以及对变量所能执行的操作集。 值：变量所占据的存储单元中的内容。 生命期：在程序执行期间变量存在的时段。 作用域：在程序中变量被引用的语句范围。,North China Electric Power University,2)指针变量 C+中指针变量是一个Type *类型的变量，Type为任意已知类型。 例：int n=8; int *p; p= 其中，j是对变量i的一个引用,i的值改变时，j的值也跟着改变。,North China Electric Power University,2.函数和参数传递,1)函数 C+中有两种函数：常规函数和成员函数。其定义都包含四个部 分：函数名、形式参数表、返回类型和函数体。函数的返回值通 过函数体中的return语句返回。return语句的作用是返回一个与 返回类型相同类型的值，并中断程序的运行。 2)参数传递 在C+中调用函数时传递给形参表的实参必须与形参在类型、个 数、顺序上保持一致。参数的传递有两种方式： 按值传递：把实参的值传递给函数局部工作区相应的副本中。函 数使用副本执行必要的计算。 按引用传递：需将形参声明为引用类型，即在参数名前加上符号 &，当一个实参与一个引用类型结合时，传递的不 是实参的值，而是实参的地址。函数通过地址存取 被引用的实参，执行函数调用后，实参的值将发生 改变。,North China Electric Power University,例：void Swap(int 在C+中数组参数的传递属特殊情形。数组作为形参可按值传递 方式声明，但事实上采用引用传递方式。实际传递的是数组第一 个元素的地址。因此在函数体内对于形参数组所做出的任何改变 都会在实参数组中反映出来。,3.C+的类 C+的类由四个部分组成： 1)类名； 2)数据成员； 3)函数成员； 4)访问级别。,North China Electric Power University,class Rectangle public: Rectangle(int x1 ,int y1,int h,int w)/构造函数 this.x1=x1;this.y1=y1;this.h=h;this.w=w; Rectangle() /析构函数 int GetHeight();/矩形的高 int GetWidth();/矩形的宽 private: int x1,y1,h,w;/(x1,y1)是矩形左下角的坐标，h是高 ; /w是宽 int Rectangle:GetHeight() return h; int Rectangle:GetWeight() return w;,North China Electric Power University,4.类的对象 下面的代码说明了如何声明类Rectangle的对象，以及 如何调用其成员函数。 Rectangle r(0,0,2,3); Rectangle s(0,0,3,4); Rectangle *t= 5.构造函数和析构函数 构造函数：用于初始化一个对象的函数，与类名相同，不能有返 回值和返回类型。 析构函数：用于在一个对象被撤销时删除其数据成员。析构函数 名与类名相同，并在前面加上符号“” 。,North China Electric Power University,North China Electric Power University,6.运算符重载 C+允许为用户定义的数据类型重载运算符。 下面的代码段实现对类Rectangle的运算符“=”的重载。 bool Rectangle:operator=(const Rectangle 其中用到C+中的保留字this,在类的成员函数内部，this表示 一个指向调用该成员函数的对象的指针，因此该对象也可用*this 来表示。 经重载运算符“=”后，即可用运算符“=”来判定两个 Rectangle对象是否相同。,North China Electric Power University,7.友元函数 在类的声明中可使用保留字friend来定义友元函数。友元函 数实际上并不是类的成员函数，它可以是一个常规函数，也可以 是另一个类的成员函数。如果想通过这个函数来存取类的私有成 员和保护成员，就必须在类的声明中给出函数的原型，并在前面 加上friend。 8.内联函数 在函数前面加上一个inline前缀，该函数就被定义成一个内 联函数。内联函数的保留字inline告诉编译器在任何调用该函数 的地方直接插入内联函数的函数体。 9.模板 模板是C+提供的一种新机制，用于增强类和函数的可重用 性。通过使用模板可以定义一个通用的函数max如下: template Type max(Type x,Type y) return xy?x:y;,North China Electric Power University,上述模板定义了一个max函数的家族系列，分别对应用于不 同的类型Type,编译器根据需要创建合适的max函数。 例：int i=max(1,2); double x=max(1.0,2.0); 除了定义通用函数外，模板还可以定义通用类。 例如：利用模板，可以定义一个通用的栈类如下： template class Stack public: Stack(int MaxStackSize=100); bool IsFull(); bool IsEmpty(); void Push(const Type,North China Electric Power University,template Stack:Stack(int MaxStackSize) MaxSize=MaxStackSize; stack=new TypeMaxSize; top= -1; template inline bool Stack:IsFull() if(top=MaxSize-1) return true; else return false; template inline bool Stack:IsEmpty() if(top= -1) return true; else return false; ,North China Electric Power University,template void Stack:Push(const Type,North China Electric Power University,10.动态存储分配 1)运算符new C+的运算