数学理论复杂性

《数学理论复杂性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京师范大学数学学院杨进goodskyfly@163.com网络与信息安全2021/7/22问题复杂性第2章信息安全数学基础（计算复杂性）算法复杂性2021/7/22问题复杂性第2章信息安全数学基础（计算复杂性）算法复杂性2021/7/22为什么要学习计算复杂性？计算复杂性是研究密码分析对于计算量的需求和密码分析的困难程度，从而得出这些密码技术和算法在现有可行的条件下是否具有足够的安全性。学习计算复杂性，需要掌握两个概念：问题算法计算复杂性2021/7/22问题（problem）（问题）定义：即需要回

2、答的一般性提问:它通常含有若干个参数。对于一个问题进行描述应该包括两方面的内容：必须对问题的所有给定参数给出一般性描述；必须描述该问题的答案（或解）应该满足的性质。当问题的所有参数都有了确定的取值时，我们称得到了该问题的一个实例（instance）。2021/7/22算法（algorithm）定义（算法）：即求解某个问题的一系列具体步骤（通常被理解为求解所需的通用计算程序）。算法总是针对具体问题而言的，求解一个问题的算法通常不止一个。当某个算法能够回答一个问题的任何实例时，我们称该算法能够回答这个问题

3、。当一个问题至少有一个能够回答该问题的算法时，我们称该问题可解（resolvable），否则称该问题不可解（unresolvable）。2021/7/22算法（algorithm）（续）有关算法的几点注释：算法总有输入和输出算法输入大小一般用输入变量的长度（单位为位）来表示一般来说，算法用某种编程语言来实现的计算机程序一般来说，我们仅仅关注解决问题最有效的算法2021/7/22问题与算法问题：如何求解两个整数a和b的最大公约数？参数：a和b问题实例：a＝20，b＝30算法：利用因子分解求a＝20和b＝

4、30的最大公约数a＝2×2×5b＝2×3×5因此a和b的最大公约数是2×5＝102021/7/22算法复杂性（算法复杂度）定义：即度量该算法所需的计算能力，包括：时间复杂性T（timecomplexity）；空间复杂性S（spacecomplexity）；信道带宽；数据总量；……2021/7/22算法复杂性（续）计算复杂性的表示符号为“O”（称为“大O”，即算法的阶号），表示计算复杂性的数量级好处：使算法复杂性度量与处理器的运行速度和指令运行时间无关；明确地揭示了输入的数据长度对算法复杂性的影响。20

5、21/7/22算法复杂性（续）算法常见复杂性分类（1）常数算法（constantAlgorithm）：如果运行时间是O(1)，即该算法的复杂性不依赖于n。（2）线性算法（linearAlgorithm）：如果运行时间是O(n)。（3）多项式算法（polynomialAlgorithm）：如果运行时间是O(nm)，其中m是一个常数。具有多项式复杂性的算法族被称为多项式时间算法。（4）超多项式算法（superpolynomialAlgorithm）：如果运行时间是，其中c是一个常数，而s(n)是关于n的大

6、于常数而小于线性的函数。（5）指数算法（exponentialAlgorithm）：如果运行时间是，其中t是大于1的常数，f(n)是关于n的多项式函数。2021/7/22算法复杂性（续）算法常见复杂性分类一般而言，常数算法、线性算法、多项式算法和超多项式算法统称为多项式算法。所谓多项式，就是具有下列形式的一个函数：其中，k和ck是常数，且ci称≠0为。当k>0时，k称为多项式的次数，ci称为多项式的系数。2021/7/22算法复杂性算法的分类及其运行时间算法类型复杂性运算次数n＝106时间多项式算法常

7、数算法O(1)11微秒线性算法O(n)1061秒二次多项式算法O(n2)101211.6天三次多项式算法O(n3)101832,000年指数算法O(2n)1030103010301006年算法复杂性（续）2021/7/22算法复杂性算法复杂度的增长速度算法复杂性（续）亚指数指数多项式2021/7/22算法复杂性（续）研究问题的内在复杂性，即在图灵机上解决最难的问题实例所需的最小时间和空间条件。图灵机是一种具有无限读、写存储带的有限状态机，可以被当作一个实际可用的计算模型。2021/7/22问题复杂性第

8、2章信息安全数学基础（计算复杂性）算法复杂性2021/7/22问题复杂性图灵机分为两类：确定性图灵机。非确定性图灵机2021/7/22问题复杂性（续）确定性图灵机。确定性图灵机的输出结果只取决于输入和初始状态。因此，对于具有相同输入和初始状态，运行一个确定性图灵机所得到的结果是完全相同的。非确定性图灵机：能够进行猜测。求解一个问题分两个阶段：猜测阶段和验证阶段。2021/7/22图灵机图灵机包括一个有限状态控制单元、k（≥1）条纸带（Tape）和k个读写