图论第1章 预备知识.ppt

这里我们需要规定：0.199…=0.200…，为了保证上述函数值的唯一性，如遇到上述情形时，统一取后者表示。 设y是区间[0，1]上的一个数，表示为： 显然y可以构造出来，且y与上面的任何一个函数值都不相等，所以有 ，即 f不是满射。 （2）和（1）的证明类似，下面证明任何从A到P（A）的函数都不是满射。 设 为从A到P（A）的任一函数，构造集合B 则 ，但对任意 ，都有 ，所以 有 ，即 g不是满射。 由上述定理，这说明不存在最大的基数，将已知的基数按从小到大的顺序排列就得到： 算法的复杂度分析 一个算法是有限指令的集合 有限性:任何算法都会在有限条指令执行完 后结束。 确定性:算法的每一步有精确的定义。 输入有零个或多个输入，且输入取自特定 的对象集合。 输出 :有一个或多个输出与输入有某种特定关系。 唯一性 :每一步执行后所得到的中间结果是唯一的，且仅依赖于输入和先前步骤的结果.。 通用性:算法适用于一类输入。 问题的描述:是对参数进行描述，指出其解是满足什么性质的命题。 实例 :给问题的全体参数都指定了确定的值便得到一个问题的实例。 A是问题P的算法，若算法A对问题P的每个实例都给出正确答案。 问题P算法可解，若存在一个算法解答问题P。 算法分析 算法效率的衡量方法1 事后统计 利用计算机内记时功能。 缺点： ?必须先运行依据算法编制的程序； ?所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣。 算法效率的衡量方法2 事前分析估计 一个高级语言程序在计算机上运行所消耗的时间取决于：?依据的算法选用何种策略?问题的规模?程序语言?编译程序产生机器代码质量?机器执行指令速度 时间复杂度和空间复杂度 算法的时间度量 从算法中选取一种对于研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法执行的时间度量。 例， for ( j = 1 ；j=n ；j++ ) X = X + 1 ； for ( i = 1 ；i=n ；i++ ) (c) for ( i = 1 ；i=n ；i++ ) X = X + 1 ； (b) X = X + 1 ； (a) 基本操作重复执行的次数分别为 1，n，n2 算法复杂度 问题的规模(n)：或大小。如：矩阵的阶数、图的结点个数、被分类序列的正整数个数…… 时间复杂度：算法的所需的时间和问题规模的函数。记为 T(n)。当 n- ∞ 时的时间复杂性，被称之为渐进时间复杂度。 空间复杂度：算法的所需的空间和问题规模的函数。记为 S(n)。当 n- ∞ 时的时间复杂性，被称之为渐进空间复杂度。 给定两个正值函数 f 和 g，考虑以下定义： 定义： 如果存在正数c和N，对于所有的n≥N，有f(n)≤cg(n), 则f(n)=O(g(n))。 上述定义表明，如果对于足够大的n，或大于某自然数N的n，存在正数c，使 f 不大于cg，则 f 是g的大O符号。 大O符号 例： f(n)=2n2+3n+1=O(n2) 在这里，g(n)=n2，c和N的可选值如表所示： 表 对于函数f(n)=2n2+3n+1=O(n2)，根据大O定义计算得到的c和N的不同值 N 1 2 3 4 5 … ∞ c ≥6 ≥ ≥ ≥ ≥ … 算法时间复杂度,一般均表示为以下几种数量级的形式(n为问题的规模,c为一常量)： Ο(1)称为常数 Ο(logn)称为对数级 Ο(n)称为线性级 Ο(nc)称为多项式级 Ο(cn)称为指数级 Ο(n!)称为阶乘级 常见算法时间复杂度：O(1): 表示算法的运行时间为常量O(n): 表示该算法是线性算法O(㏒2n): 二分查找算法O(n2): 对数组进行排序的各种简单算法，例如选择排序。O(n3): 做两个n阶矩阵的乘法运算O(2n): 求具有n个元素集合的所有子集的算法O(n!): 求具有N个元素的全排列的算法 O(1)O(㏒2n)O(n)O(n2)O(2n) 时间复杂度按数量级递增排列依次为： 常数阶O(1)、 对数阶O(log2n)、