算法的评价 算的算种 法的复性:是对算法计算所需的时间和空间 漆的时间复杂性:是对算法计算所需时间的 度 漆的空间复杂性:是对算法计算所需空间的 种度量。 复杂性度量函数:算法在求解一类问题的过程中 随回题规模大小变 起的算法中抽象的基本运 算执行的次数或存储空间 变化规律。 例如:f(n)=2n2+3n+1=O(m2),读作n2阶,其中,n为 问题规模。 返回
算法的评价 ◼ 算法的复杂性：是对算法计算所需的时间和空间 的一种度量。 ◼ 算法的时间复杂性：是对算法计算所需时间的一 种度量。 ◼ 算法的空间复杂性：是对算法计算所需空间的一 种度量。 ◼ 复杂性度量函数：算法在求解一类问题的过程中 随问题规模大小变化引起的算法中抽象的基本运 算执行的次数或存储空间量的变化规律。 ◼ 例如：f (n)=2n2+3n+1=O(n2 ),读作n 2阶,其中，n为 问题规模。 返回
证比求易问题 个中国人问题,洪加威,1980 国王:艾述,宰相:孔唤石,公主:秋碧贞楠 求数8770428644836899的一个真因子。 证明23092871是8770428644836899的一个真因子。 问题规模17位,小因子不超过9位 顺序算法与并行算法 对偶性原理:在并行计算模型上,计算的时间与空间可 以互换。 相似性原理:所有合理的、功能足够强的计算模型不仅 可以相互模拟计算,而且它们相互模拟时,同时使用本质 相同的并行时间,本质上相同的空间,本质上相同的顺 序时间
证比求易问题 ◼ 三个中国人问题，洪加威，1980 国王：艾述，宰相：孔唤石，公主：秋碧贞楠 求数8770428644836899的一个真因子。 证明23092871是8770428644836899的一个真因子。 问题规模17位，小因子不超过9位 顺序算法与并行算法 ◼ 对偶性原理：在并行计算模型上，计算的时间与空间可 以互换。 ◼ 相似性原理：所有合理的、功能足够强的计算模型不仅 可以相互模拟计算，而且它们相互模拟时，同时使用本质 上相同的并行时间，本质上相同的空间，本质上相同的顺 序时间。 返回
NP完全性问题 ■难解型问题:没有多项式时间复杂性算法的问题。 ■P类问题:存在图灵机可计算的多项式时间复杂性 算法的问题。 NP问题:存在非确定图灵机可计算的多项式时间 复杂性算法的问题 NP完全性问题:NP问题中若有一个问题找到了 多项式时间复杂性算法,这个类中的其它问题也 可找到多项式时间复杂性算法,则P=NP。返回
NP完全性问题 ◼ 难解型问题：没有多项式时间复杂性算法的问题。 ◼ P类问题：存在图灵机可计算的多项式时间复杂性 算法的问题。 ◼ NP问题：存在非确定图灵机可计算的多项式时间 复杂性算法的问题。 ◼ NP完全性问题：NP问题中若有一个问题找到了 多项式时间复杂性算法，这个类中的其它问题也 可找到多项式时间复杂性算法，则P=NP。 返回
算法的概念 算法 有穷规则的集合,其中之规则确定了 个解决某二特定类型问题的运算序列。此 算法的规则序列须满是如下五个重要条件 1、有穷性:算法必须总是在执行有穷步之后结束; 2、确定性:算法的每一个步骤必须是确切地定乂 的 3、输入:算法有零个或多个输入 4、输出:算法有一个或多个输出; 5:能行性:算法中有待执行的运算和操作必须是 相当基本的
算法的概念 ◼ 算法：一个有穷规则的集合，其中之规则确定了 一个解决某一特定类型问题的运算序列。此外， 算法的规则序列须满足如下五个重要条件： 1、有穷性：算法必须总是在执行有穷步之后结束； 2、确定性：算法的每一个步骤必须是确切地定义 的； 3、输入：算法有零个或多个输入； 4、输出：算法有一个或多个输出； 5：能行性：算法中有待执行的运算和操作必须是 相当基本的。 返回
布尔代数 布尔,G. Boole,19世纪,英国,自学成才 集合代数:集合、集合的运算与性质 集合A,A的补集A’,空集Φ,全集1,属于∈,相 并 集合与命题 布尔代数实现了从一组逻辑公理出发,依靠代数 演篁来推导逻辑定律或定理,用数学的方法来研 究人的思维结构。 语义推导与语法推导 布尔代数、数字逻辑与电子计算机 返回
布尔代数 ◼ 布尔，G. Boole,19世纪，英国，自学成才 ◼ 集合代数：集合、集合的运算与性质 集合A，A的补集A’，空集Ф，全集1，属于，相 等=，包含，交，并 ◼ 集合与命题 ◼ 布尔代数实现了从一组逻辑公理出发，依靠代数 演算来推导逻辑定律或定理，用数学的方法来研 究人的思维结构。 ◼ 语义推导与语法推导 ◼ 布尔代数、数字逻辑与电子计算机 返回