Chapter1_算法分析.ppt

一维数组 ： 为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x声明为一个float类型的指针。然后用new为数组动态地分配存储空间。 例： float ?x=new float[n]； 创建一个大小为n的一维浮点数组。运算符new分配n个浮点数所需的空间，并返回指向第一个浮点数的指针。 然后可用x[0]，x[1]，…，x[n-1]来访问每个数组元素。 运算符delete ： 当动态分配的存储空间已不再需要时应及时释放所占用的空间。 用运算符delete来释放由new分配的空间。 例： delete y； delete [ ]x； 分别释放分配给?y的空间和分配给一维数组x的空间。 动态二维数组 ： 创建类型为Type的动态工作数组，这个数组有rows行和cols列。 template class Type void Make2DArray(Type** x,int rows, int cols) { x=new Type*[rows]; for (int i=0;irows;i++) x[i]=new Type[cols]; } 当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用的空间。首先释放在for循环中为每一行所分配的空间。然后释放为行指针分配的空间。 释放空间后将x置为0，以防继续访问已被释放的空间。 template class Type void Delete2DArray(Type** x,int rows) { for (int i=0;irows;i++) delete []x[i]; delete []x; x=0; } * * * * * * * * * * * * * * * * * * 符号O 定义1 对于足够大的n，t(n)的上界由g(n)的常数倍来确定，即： 记为t(n) ∈O(g(n)) t(n) ≤ cg(n)，c为常数 n ∈O(n2) 100n+5 ∈O(n2) n(n-1)/2 ∈O(n2) 符号Ω 定义2 对于足够大的n，t(n)的下界由g(n)的常数倍来确定，即： 记为t(n) ∈ Ω(g(n)) t(n) ≥ cg(n)，c为常数 n3∈Ω (n2) n(n+1)∈Ω (n2) 4n2+5 ∈Ω (n2) 符号Θ 定义3 对于足够大的n，t(n)的上界和下界由g(n)的常数倍来确定，即： 记为t(n) ∈ Θ(g(n)) c2g(n) ≤ t(n) ≤ c1g(n)，c1,c2为常数 n2+3n+2∈Θ (n2) n(n-1)/2∈Θ (n2) 4n2+5 ∈Θ (n2) 渐进符号的有用特性 定理 如果t1(n) ∈O(g1(n))并且t2(n) ∈O(g2(n))，则 t1(n)+ t2(n) ∈O(max{(g1(n), g2(n)}) 对于符号Ω和Θ，该定理也成立。 该定理表明：当算法由两个连续执行部分组成时，该算法的整体效率由具有较大增长次数的那部分所决定。 利用极限比较增长次数 前两种情况意味着t(n) ∈ O(g(n)) 后两种情况意味着t(n) ∈ Ω(g(n)) 第二种情况意味着t(n) ∈ Θ(g(n)) 基本的效率类型 常量(1)、对数(logn)、线性(n)、nlogn、平方(n2)、立方(n3)、指数(2n)、阶乘(n!) 算法分析中常见的复杂性函数 常见的算法时间复杂度由小到大依次为： Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!) Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。 算法分析的基本法则 非递归算法： （1）for / while 循环 循环体内计算时间*循环次数； （2）嵌套循环 循环体内计算时间*所有循环次数； （3）顺序语句 各语句计算时间相加； （4）if-else语句 if语句计算时间和else语句计算时间的较大者。 分析非递归算法效率的通用方案 决定用那些参数作为输入规模的度量。 找出算法的基本操作。 检查基本操作的执行次数是否只依赖输入规模。 建立一个算法基本操作执行次数的求和表达式。 利用求和运算的标准公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数。 O(1)Temp=i;i=j;j=