第一章算法分析的数学基础
第一章 算法分析的 数学基础
本章内容复杂性函数的阶和的估计与界限■递归方程
本章内容 ◼ 复杂性函数的阶 ◼ 和的估计与界限 ◼ 递归方程 2
一些记号[x]表示小于等于x的最大整数[x]表示大于等于x的最小整数x-1<[x≤x≤[xl<x+1 logn = log2 n, lgn = log2nlnn = logen?
一些记号 ◼ 𝒙 表示小于等于𝒙的最大整数 ◼ 𝒙 表示大于等于𝒙的最小整数 𝒙 − 𝟏 < 𝒙 ≤ 𝒙 ≤ 𝒙 < 𝒙 + 𝟏 ◼ log 𝒏 = log𝟐 𝒏 ，lg 𝒏 = log𝟐 𝒏 ◼ ln 𝒏 = log𝒆 𝒏 3
复杂性函数的阶渐近复杂性当输入规模趋于极限情形时（相当大）的复杂性表示复杂性阶的三个记号 T(n)=O(f(n)若存在c>0，和正整数no≥1，使得当nzn.时，有T(n)≤c*f(n)成立。给出算法复杂度的上界，不可能比c*f(n)更大则当>e.g.T(n)=3n3+2n2, 取c=5, n=1,f(n)=n3,n≥n(=1)时，有3n3+2n2≤5n3..:.T(n)=O(n3)
复杂性函数的阶 ◼ 渐近复杂性 当输入规模趋于极限情形时(相当大)的复杂性 表示复杂性阶的三个记号 T(n)=O(f(n)) ➢ 若存在c > 0，和正整数n0≥1，使得当n≥n0时，有 T(n)≤c*f(n)成立。 ➢ 给出算法复杂度的上界，不可能比c*f(n)更大 ➢ e.g. T(n)=3n3+2n2，取c=5，n0=1，f(n)=n3，则当 n≥n0 (=1)时，有3n3+2n2≤5n3 . ∴T(n)= O(n3 ) 4
复杂性函数的阶渐近复杂性当输入规模趋于极限情形时（相当大）的复杂性表示复杂性阶的三个记号 T(n)=2(f(n))若存在c>0，和正整数n≥1，使得当nzn.时，有T(n)≥c*f(n)成立。给出算法复杂度的下界，不可能比c*f(n)更小>e.g.T(n)=3n3+2n2，取c=3，no=1，f(n)=n3，则当n≥no(=1)时，有3n3+2n2≥3n3，:.T(n)=Q2(n3)S
复杂性函数的阶 ◼ 渐近复杂性 当输入规模趋于极限情形时(相当大)的复杂性 表示复杂性阶的三个记号 T(n)=Ω(f(n)) ➢ 若存在c > 0，和正整数n0≥1，使得当n≥n0时，有 T(n)≥c*f(n)成立。 ➢ 给出算法复杂度的下界，不可能比c*f(n)更小 ➢ e.g. T(n)=3n3+2n2，取c=3，n0=1，f(n)=n3，则当 n≥n0 (=1)时，有3n3+2n2≥3n3 ，∴T(n)=Ω(n3 ) 5