- 1、本文档共213页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
图论第1章 预备知识
这里我们需要规定: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)、
您可能关注的文档
- 国际商务谈判的“需要理论”.ppt
- 国际商法试题真题.doc
- 国际政治经济学—第四章.ppt
- 国际投资学课件第8章-国际投资环境.ppt
- 国际投资学期末复习题2015.ppt
- 国际收支调节手段与理论.ppt
- 国际物流6-商品检验.ppt
- 国际多式联运小析.pptx
- 国际商务合同的文体与翻译chapter2-3.ppt
- 国际焊工理论培训 不锈钢.ppt
- 第12课 大一统王朝的巩固 课件(20张ppt).pptx
- 第17课 君主立宪制的英国 课件.pptx
- 第6课 戊戌变法 课件(22张ppt).pptx
- 第三章 物态变化 第2节_熔化和凝固_课件 (共46张ppt) 人教版(2024) 八年级上册.pptx
- 第三章 物态变化 第5节_跨学科实践:探索厨房中的物态变化问题_课件 (共28张ppt) 人教版(2024) 八年级上册.pptx
- 2025年山东省中考英语一轮复习外研版九年级上册.教材核心考点精讲精练(61页,含答案).docx
- 2025年山东省中考英语一轮复习(鲁教版)教材核心讲练六年级上册(24页,含答案).docx
- 第12课近代战争与西方文化的扩张 课件(共48张ppt)1.pptx
- 第11课 西汉建立和“文景之治” 课件(共17张ppt)1.pptx
- 唱歌 跳绳课件(共15张ppt内嵌音频)人音版(简谱)(2024)音乐一年级上册第三单元 快乐的一天1.pptx
文档评论(0)