数学理论复杂性省公开课一等奖全国示范课微课金奖课件.pptx

北京师范大学数学学院杨进goodskyfly@163.com网络与信息安全

2025/2/21第1页

问题复杂性第2章信息安全数学基础（计算复杂性）算法复杂性2025/2/21第2页

问题复杂性第2章信息安全数学基础（计算复杂性）算法复杂性2025/2/21第3页

为何要学习计算复杂性？计算复杂性是研究密码分析对于计算量需求和密码分析困难程度，从而得出这些密码技术和算法在现有可行条件下是否含有足够安全性。学习计算复杂性，需要掌握两个概念：问题算法计算复杂性2025/2/21第4页

问题（problem）（问题）定义：即需要回答普通性提问:它通常含有若干个参数。对于一个问题进行描述应该包含两方面内容：必须对问题全部给定参数给出普通性描述；必须描述该问题答案（或解）应该满足性质。当问题全部参数都有了确定取值时，我们称得到了该问题一个实例（instance）。2025/2/21第5页

算法（algorithm）定义（算法）：即求解某个问题一系列详细步骤（通常被了解为求解所需通用计算程序）。算法总是针对详细问题而言，求解一个问题算法通常不止一个。当某个算法能够回答一个问题任何实例时，我们称该算法能够回答这个问题。当一个问题最少有一个能够回答该问题算法时，我们称该问题可解（resolvable），不然称该问题不可解（unresolvable）。2025/2/21第6页

算法（algorithm）（续）相关算法几点注释：算法总有输入和输出算法输入大小普通用输入变量长度（单位为位）来表示普通来说，算法用某种编程语言来实现计算机程序普通来说，我们仅仅关注处理问题最有效算法2025/2/21第7页

问题与算法问题：怎样求解两个整数a和b最大条约数？参数：a和b问题实例：a＝20，b＝30算法：利用因子分解求a＝20和b＝30最大条约数a＝2×2×5b＝2×3×5所以a和b最大条约数是2×5＝102025/2/21第8页

算法复杂性（算法复杂度）定义：即度量该算法所需计算能力，包含：时间复杂性T（timecomplexity）；空间复杂性S（spacecomplexity）；信道带宽；数据总量；……2025/2/21第9页

算法复杂性（续）计算复杂性表示符号为“O”（称为“大O”，即算法阶号），表示计算复杂性数量级好处：使算法复杂性度量与处理器运行速度和指令运行时间无关；明确地揭示了输入数据长度对算法复杂性影响。2025/2/21第10页

算法复杂性（续）算法常见复杂性分类（1）常数算法（constantAlgorithm）：假如运行时间是O(1)，即该算法复杂性不依赖于n。（2）线性算法（linearAlgorithm）：假如运行时间是O(n)。（3）多项式算法（polynomialAlgorithm）：假如运行时间是O(nm)，其中m是一个常数。含有多项式复杂性算法族被称为多项式时间算法。（4）超多项式算法（superpolynomialAlgorithm）：假如运行时间是，其中c是一个常数，而s(n)是关于n大于常数而小于线性函数。（5）指数算法（exponentialAlgorithm）：假如运行时间是，其中t是大于1常数，f(n)是关于n多项式函数。2025/2/21第11页

算法复杂性（续）算法常见复杂性分类普通而言，常数算法、线性算法、多项式算法和超多项式算法统称为多项式算法。所谓多项式，就是含有以下形式一个函数：其中，k和ck是常数，且ci称≠0为。当k0时，k称为多项式次数，ci称为多项式系数。2025/2/21第12页

算法复杂性算法分类及其运行时间算法类型复杂性运算次数n＝106时间多项式算法常数算法O(1)11微秒线性算法O(n)1061秒二次多项式算法O(n2)101211.6天三次多项式算法O(n3)101832,0指数算法O(2n)10301030103010算法复杂性（续）2025/2/21第13页

算法复杂性算法复杂度增加速度算法复杂性（续）亚指数指数多项式2025/2/21第14页

算法复杂性（续）研究问题内在复杂性，即在图灵机上处理最难问题实例所需最小时间和空间条件。图灵机是一个含有没有限读、写存放带有限状态机，能够被看成一个实际可用计算模型。2025/2/21第15页

问题复杂性第2章信息安全数学基础（计算复杂性）算法复杂性2025/2/21第16页

问题复杂性图灵机分为两类：确定性图灵机。非确定性图灵机2025/2/21第17页

问题复杂性（续）确定性图灵机。确定性图灵机输出结果只取决于输入和初始状态。所以，对于含有相同输入和初始状态，运行一个确定性图灵机所得到结果是完全相同。非确定性图灵机：