1.2现实上的可计算一一计算复杂性理论 内容 算法复杂度—算法所使用的时间、空间的估计 问题复杂度——估计问题的难度 术语和概念 问题 算法 算法的时间复杂度 复杂度函数的阶 多项式时间的算法与指数时间的算法 问题的复杂度分析
6 1.2 现实上的可计算――计算复杂性理论 内容 算法复杂度——算法所使用的时间、空间的估计 问题复杂度——估计问题的难度 术语和概念 问题 算法 算法的时间复杂度 复杂度函数的阶 多项式时间的算法与指数时间的算法 问题的复杂度分析
高度并行可解 现实上可解 理论上可解 理论上不可解
7
二算法的时间复杂度 最坏情况下的时间复杂度 算法求解输入规模为n的实例所需要的最长时间Wm) 平均情况下的时间复杂度 算法求解输入规模为n的实例所需要的平均时间A(m) 复杂度表示 针对问题选择基本运算 将基本运算次数表示为输入规模的函数
8 二 算法的时间复杂度 最坏情况下的时间复杂度 算法求解输入规模为 n 的实例所需要的最长时间 W( n) 平均情况下的时间复杂度 算法求解输入规模为 n 的实例所需要的平均时间 A ( n) 复杂度表示 针对问题选择基本运算 将基本运算次数表示为输入规模的函数
例搜索问题 输入:非降顺序排列的数组L,元素数为n.数x 输出:六若x在L中,j是x首次出现的序标; 否则j=0 算法顺序搜索 假设x在L中的概率为p x在L中不同位置是等概分布的,则 w(n)=n ∑ P(n+1) +(1-p)n 十 p)n 2
9 ∑ = + − + = + − = = n i p n p n p n n p A n i W n n 1 (1 ) 2 ( 1) ( ) (1 ) ( ) 例 搜索问题 输入：非降顺序排列的数组 L，元素数为 n. 数 x 输出：j. 若 x 在 L 中，j 是 x 首次出现的序标； 否则 j = 0 算法 顺序搜索 假设 x 在 L 中的概率为 p x 在 L 中不同位置是等概分布的，则
复杂度函数的阶 设∫和g是定义域为自然数集N上的函数 f(n=o(g(n)) 若存在正数c和m使得对一切心有0≤fm)cg(n) f(m)=(g(m) 若存在正数c和h使得对一切n有0≤cg(m)≤八m) f(m)=0(g(m) 对所有正数c<1存在m使得对一切n≥1有0≤f(m)<cg(m) f(n)=⊙(g(m) f(n=O(g(n)A f(n)=2(g(n) O(1表示常数函数
10 复杂度函数的阶 设 f 和 g 是定义域为自然数集 N 上的函数 f(n)=O(g(n)). 若存在正数 c 和 n0使得对一切 n≥n0有 0≤f(n)≤cg(n) f(n)= Ω(g(n)). 若存在正数 c 和 n0使得对一切 n≥n0有 0≤cg(n)≤ f(n) f(n)=o(g(n)). 对所有正数 c<1 存在 n0使得对一切 n≥n0有 0≤f(n)<cg(n) f(n)=Θ(g(n)) f(n)=O(g(n)) 且 f(n)=Ω(g(n)) O(1)表示常数函数