算法设计与分析复习

算法概述算法是若干指令的有穷序列，满足性质：(1)输入(2)输出 (3)确定性 (4)有限性。算法复杂性分析主要包括空间复杂性和时间复杂性。算法复杂性分析（1）渐近上界记号OO(g(n)) = { f

第1章 算法概述 算法是若干指令的有穷序列，满足性质： (1)输入(2)输出(3)确定性(4)有限性。 算法复杂性分析主要包括空间复杂性和时间复杂性。 算法复杂性分析 O （1）渐近上界记号 f) O(g(n))=(ncn0nn0 fncgn {|存在正常数和使得对所有有：0()() ³££ } W （2）渐近下界记号 g(n))f(n)cn0nn0cg(n)f(n) W (={|存在正常数和使得对所有有：0 ³££ } （3）紧渐近界记号 Q gnfnc,cnnncgn (())={()|存在正常数12和0使得对所有0有：1() Q³£ fncgn ()2()} £ O gngngn 定理1：(())=(())(()) QÇW 最常见的多项式时间算法的渐近时间复杂度 23 nnnnnn O(1)＜O(log)＜O()＜O(log)＜O()＜O() 最常见的指数时间算法的渐近时间复杂度 nn nn O(2)＜O(！)＜O() 通用分治递推式 nn/ba 大小为的原问题分成若干个大小为的子问题，其中个子问题需要求解， k cn 而是合并各个子问题的解需要的工作量。 NP 完全性理论 P 是所有可在多项式时间内用确定算法求解的判定问题的集合。 NP 是所有可在多项式时间内用不确定算法求解的判定问题的集合。 NPNP Î （难度）对于问题Q以及任意问题Q1NP，都有Q1∝Q，则Q是NP难度（ hard）的。 其中∝表示约化，Q1∝Q，表示Q1可以在多项式时间转化为问题Q，从而可通过 调用问题Q的算法求解。 NP Î （完全）对于问题QNP，Q是NP难度的，则称Q是NPC（NPcomplete）的。 PNPNPC 的关系