文章目录

一、小 O 记号 ( 严格渐进上界 )

如果 g(n)\rm g(n)g(n) 是 f(n)\rm f(n)f(n) 渐进上界 , 符号化表示为 f(n)=O(g(n))\rm f(n) = O(g(n))f(n)=O(g(n)) ,

如果 f(n)\rm f(n)f(n) 除以 g(n)\rm g(n)g(n) , 求 n→∞n \to \inftyn→∞ 极限为 000 时 , 符号化表示为 limn→∞f(n)g(n)=0\rm lim_{n \to \infty} \cfrac{f(n)}{g(n)} = 0limn→∞​g(n)f(n)​=0 ,

那么称 g(n)\rm g(n)g(n) 是 f(n)\rm f(n)f(n) 的 严格渐进上界 ;

严格渐进上界使用 小 o\rm oo 记号 表示 :

① n=o(n)\rm \sqrt{n} = o(n)n​=o(n)

② n=o(nloglogn)\rm n = o(n\ log\ log \ n)n=o(nloglogn)

③ nloglogn=o(nlogn)\rm n\ log\ log \ n = o(n\ log \ n)nloglogn=o(nlogn)

④ nlogn=o(n2)\rm n\ log \ n = o(n ^2)nlogn=o(n2)

⑤ n2=o(n3)\rm n ^2 = o(n ^3)n2=o(n3)

二、分析算法的时间复杂度

构造图灵机认识如下语言 :A={0k1k:k≥0}\rm A = \{ 0^k1^k : k \geq 0 \}A={0k1k:k≥0}

M1=\rm M_1 =M1​= "在长度为 n\rm nn 的字符串 w\rm ww 上进行如下计算 :

① 扫描整个带子上的字符串 , 查看 000 和 111 的顺序 , 所有的 000 必须在所有的 111 前面 ; 如果顺序错误 , 进入拒绝状态 ;

② 扫描整个带子 , 遇到一个 000 , 就划掉一个 111 ; 如果带子上存在 000 和 111 , 该操作重复进行 ;

③ 如果最后只剩下 000 或只剩下 111 , 说明 两个数字的个数不等 , 进入拒绝状态 ; 如果最后带子上只剩下空白字符 , 说明两个数字个数相等 , 进入接受状态 ; "

分析上述算法的时间复杂度 :

字符串 w="0000⋯1111⋯"\rm w = "0000 \cdots 1111 \cdots"w="0000⋯1111⋯" , 整个 字符串长度为 n\rm nn ;

① 首先从左向右扫描一遍字符串 , 如果 000 出现在 111 右边 , 说明字符串不符合条件 , 检查的字符个数最坏的情况就是遍历 n\rm nn 次 , 使用 大 O\rm OO 标记 为 : O(n)\rm O(n)O(n) ;

② 扫描带子 , 读取到一个 000 , 划掉一个 111 , 然后在掉过头来 , 读取到一个 000 , 划掉一个 111 ;

这是一个循环 , 计算循环复杂度 , 只需要考虑 每次循环花费的时间 , 和 循环次数 ;

循环的次数最坏情况是 n2\rm \cfrac{n}{2}2n​ , 还是 n\rm nn 的数量级 , 标记为 O(n)\rm O(n)O(n) ;

每次循环的花费时间步数 : 向右走 n2\rm \cfrac{n}{2}2n​ 步 , 找到 111 字符 , 删除 111 字符后 , 然后再向左 n2\rm \cfrac{n}{2}2n​ 步 回到第 000 个 , 大约是 n2\rm \cfrac{n}{2}2n​ 步 , 数量级还是 nnn , 使用 大 O\rm OO 标记 为 : O(n)\rm O(n)O(n) ;

将上述 循环次数 和 每次循环步数 大 O\rm OO 标记 相乘 , 就是该阶段的 大 O\rm OO 标记 为 : O(n)×O(n)=O(n2)\rm O(n) \times O(n) = O(n^2)O(n)×O(n)=O(n2) ;

上述 ① 和 ② 总的 大 O\rm OO 标记 为 :O(n)+O(n2)=O(n2)\rm O(n) + O(n^2) = O(n^2)O(n)+O(n2)=O(n2)