算法复杂性(续) ●●●●● ●●●● ●●0 ●●●● ●算法常见复杂性分类 般而言,常数算法、线性算法、多项式算法和超多 项式算法统称为多项式算法 所谓多项式,就是具有下列形式的一个函数: f(n=Cn+Ck_n++cn+co 其中,k和c是常数,且cz称≠0为。当k>0时,k称为多项式的 次数,c称为多项式的系数。 2021/2/10
2021/2/10 算法复杂性（续） ⚫ 算法常见复杂性分类 ⚫ 一般而言，常数算法、线性算法、多项式算法和超多 项式算法统称为多项式算法。 ⚫ 所谓多项式，就是具有下列形式的一个函数： 1 1 1 0 ( ) ... k k k k f n c n c n c n c − = + + + + − 其中，k和ck是常数，且ci称≠0为。当k>0时，k称为多项式的 次数，ci称为多项式的系数
算法复杂性(续) ●●●●● ●●●● ●●0 ●●●● 算法的分类及其运行时间 算法类型 复杂性运算次数n= 时间 106 常数算法 1微秒 线性算法 O(n)106 1秒 多项式算法二次多项式算O(m)1012 116天 法 次多项式算Om3)1018 32,000年 法 指数算法 O(2")10 301030 1030100F 2021/2/10
2021/2/10 算 法 复 杂 性 ⚫ 算法的分类及其运行时间 算法类型 复杂性 运算次数n＝ 106 时间 多项式算法 常数算法 O(1) 1 1微秒 线性算法 O(n) 106 1秒 二次多项式算 法 O(n 2 ) 1012 11.6天 三次多项式算 法 O(n 3 ) 1018 32,000年 指数算法 O(2n ) 10301030 10301006年 算法复杂性（续）
算法复杂性(续) ●●●●● ●●●● ●●0 ●●●● ●算法复杂度的增长速度 对任意常数E,c,其中0<E<1<c,有: <InInn< In n <exp vinninInnkn<n<n <c"<n'scc 亚指数 指数 多项式 2021/2/10
2021/2/10 算 法 复 杂 性 ⚫ 算法复杂度的增长速度 算法复杂性（续） ln lnln ln , 0 1 1 ln ln ln exp n n n c n n n c c c n n n n n c n c 对任意常数 ， 其中 ，有： 亚指数 指数 多项式
算法复杂性(续) ●●●●● ●●●● ●●0 研究问题的内在复杂性,即在图灵机上解决最难 的问题实例所需的最小时间和空间条件 图灵机是一种具有无限读、写存储带的有限状态 机,可以被当作一个实际可用的计算模型。 有限状态控制 读写头 单元 纸带1 纸带2 纸带n 2021/2/10 图灵机示意图
2021/2/10 算法复杂性（续） ⚫ 研究问题的内在复杂性，即在图灵机上解决最难 的问题实例所需的最小时间和空间条件。 ⚫ 图灵机是一种具有无限读、写存储带的有限状态 机，可以被当作一个实际可用的计算模型 。 有限状态控制 单元 读写头 纸带1 纸带2 纸带n 图灵机示意图
第2章信息安全数学基础(计算复杂性): ●●●● ◎算法复杂性 ◎问题复杂性 2021/2/10
2021/2/10 问题复杂性 第2章 信息安全数学基础（计算复杂性） 算法复杂性