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

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

如果 $\mathrm{f}(\mathrm{n})$ 除以 $\mathrm{g}(\mathrm{n})$ , 求 $n\to \infty$ 极限为 $0$ 时 , 符号化表示为 $\mathrm{l}\mathrm{i}{\mathrm{m}}_{\mathrm{n}\to \infty }\frac{\mathrm{f}(\mathrm{n})}{\mathrm{g}(\mathrm{n})}=0$ ,

那么称 $\mathrm{g}(\mathrm{n})$ 是 $\mathrm{f}(\mathrm{n})$ 的 严格渐进上界 ;

严格渐进上界使用 小 $\mathrm{o}$ 记号 表示 :

① $\sqrt{\mathrm{n}}=\mathrm{o}(\mathrm{n})$

② $\mathrm{n}=\mathrm{o}(\mathrm{n}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{n})$

③ $\mathrm{n}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{n}=\mathrm{o}(\mathrm{n}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{n})$

④ $\mathrm{n}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{n}=\mathrm{o}({\mathrm{n}}^2)$

⑤ ${\mathrm{n}}^2=\mathrm{o}({\mathrm{n}}^3)$

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

构造图灵机认识如下语言 : $\mathrm{A}=\{0^{\mathrm{k}}{1}^{\mathrm{k}}:\mathrm{k}\ge 0\}$

${\mathrm{M}}_1=$ "在长度为 $\mathrm{n}$ 的字符串 $\mathrm{w}$ 上进行如下计算 :

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

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

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

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

字符串 $\mathrm{w}="0000\cdots 1111\cdots "$ , 整个 字符串长度为 $\mathrm{n}$ ;

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

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

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

循环的次数最坏情况是 $\frac{\mathrm{n}}{2}$ , 还是 $\mathrm{n}$ 的数量级 , 标记为 $\mathrm{O}(\mathrm{n})$ ;

每次循环的花费时间步数 : 向右走 $\frac{\mathrm{n}}{2}$ 步 , 找到 $1$ 字符 , 删除 $1$ 字符后 , 然后再向左 $\frac{\mathrm{n}}{2}$ 步 回到第 $0$ 个 , 大约是 $\frac{\mathrm{n}}{2}$ 步 , 数量级还是 $n$ , 使用 大 $\mathrm{O}$ 标记 为 : $\mathrm{O}(\mathrm{n})$ ;

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

上述 ① 和 ② 总的 大 $\mathrm{O}$ 标记 为 : $\mathrm{O}(\mathrm{n})+\mathrm{O}({\mathrm{n}}^2)=\mathrm{O}({\mathrm{n}}^2)$

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/111032302