基本知识 计算复杂性理论 研究问题之一：NP=?P -P(Polynomic):在确定型图灵机上有多项式时间 算法的问题的集合 P (Nondeterministic Polynomial):在非确定型图 灵机上有多项式时间算法的问题的集合 一】 NP=?P:是计算机科学中非常重要而又经历了几 十年始终未解决的一个问题 -它的解决可导致一系列理论问题的解决
基 本 知 识 • 计算复杂性理论 研究问题之一：NP =? P – P (Polynomial)：在确定型图灵机上有多项式时间 算法的问题的集合 – NP (Nondeterministic Polynomial)：在非确定型图 灵机上有多项式时间算法的问题的集合 – NP =? P：是计算机科学中非常重要而又经历了几 十年始终未解决的一个问题 – 它的解决可导致一系列理论问题的解决 7
基本知识 算法分析 确定执行一个算法需要消耗的计算资源的数量的 分析过程 算法的效率或复杂度表示为一个函数，其定义域 是输入数据的规模（长度，算法大都设计成允许 任意长的输入)，值域通常是执行步数（时间复 杂度)或所需存储空间数量（空间复杂度 在算法的理论分析中，通常是估计算法渐近意义 上的复杂度 精确分析算法的复杂度有时也可行，但它通常基 于一些与具体实现相关的假设
基 本 知 识 • 算法分析 – 确定执行一个算法需要消耗的计算资源的数量的 分析过程 – 算法的效率或复杂度表示为一个函数，其定义域 是输入数据的规模（长度，算法大都设计成允许 任意长的输入），值域通常是执行步数（时间复 杂度）或所需存储空间数量（空间复杂度） – 在算法的理论分析中，通常是估计算法渐近意义 上的复杂度 – 精确分析算法的复杂度有时也可行，但它通常基 于一些与具体实现相关的假设 8
基本知识 ·可计算性、计算复杂性和算法分析的区别 算法分析致力于分析求解一个问题的某个具体算 法所需的资源量 一计算复杂性理论关注的是用所有可能算法解决同 一类问题层面上的一般性议题 可计算性理论关注的是原则上可以用算法求解的 问题（把问题区分为可计算和不可计算） 资源受限和不受限是区分计算复杂性理论和可计 算性理论的一个重要标志
基 本 知 识 • 可计算性、计算复杂性和算法分析的区别 – 算法分析致力于分析求解一个问题的某个具体算 法所需的资源量 – 计算复杂性理论关注的是用所有可能算法解决同 一类问题层面上的一般性议题 – 可计算性理论关注的是原则上可以用算法求解的 问题（把问题区分为可计算和不可计算） – 资源受限和不受限是区分计算复杂性理论和可计 算性理论的一个重要标志 9
复杂性的计量 两种查找算法的效率比较 int search(int val){/顺序查找 int j=0; int a m无重复且已按从小到大排序 while(ali]val &j<m -1){ j=j+1; if (alil =val) return j; else return -1; }∥在最坏情况下，需要把val与a的所有分量比较
复杂性的计量 • 两种查找算法的效率比较 int search(int val) { // 顺序查找 int j = 0; //int a[m]无重复且已按从小到大排序 while(a[j] < val && j < m −1) { j = j +1; } if (a[j] == val) { return j; } else { return −1; }// 在最坏情况下，需要把val与a的所有分量比较 } 10
复杂性的计量 两种查找算法的效率比较 int search(int val){∥二分查找 int i,j,k; ,/int a m无重复且已按从小到大排序 i=0;j=m-1; while(i <j) k=i+(j-i)/2; if (val <a[k)j=k-1; if (val >a k)i=k+1; 3 if (j-i==-1)freturn 1;}else {return k;} }∥在最坏情况下，只需要把val与a的1og2m个 ∥分量比较，显然效率高于前一个算法
复杂性的计量 • 两种查找算法的效率比较 int search(int val) { // 二分查找 int i, j, k; //int a[m]无重复且已按从小到大排序 i = 0; j = m −1; while(i <= j) { k = i + (j − i)/2; if (val <= a[k]) j = k − 1; if (val >= a[k]) i = k + 1; } if (j − i == − 1) {return − 1;} else {return k;} } // 在最坏情况下，只需要把val与a的log2 m个 // 分量比较，显然效率高于前一个算法 11