文章目录
一、小 O 记号 ( 严格渐进上界 )
二、分析算法的时间复杂度
一、小 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→∞ 极限为 0 00 时 , 符号化表示为 l i m n → ∞ f ( n ) g ( n ) = 0 \rm lim_{n \to \infty} \cfrac{f(n)}{g(n)} = 0lim
n→∞
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 ( n l o g l o g n ) \rm n = o(n\ log\ log \ n)n=o(n log log n)
③ n l o g l o g n = o ( n l o g n ) \rm n\ log\ log \ n = o(n\ log \ n)n log log n=o(n log n)
④ n l o g n = o ( n 2 ) \rm n\ log \ n = o(n ^2)n log n=o(n
2
)
⑤ n 2 = o ( n 3 ) \rm n ^2 = o(n ^3)n
2
=o(n
3
)
二、分析算法的时间复杂度
构造图灵机认识如下语言 : A = { 0 k 1 k : k ≥ 0 } \rm A = \{ 0^k1^k : k \geq 0 \}A={0
k
1
k
:k≥0}
M 1 = \rm M_1 =M
1
= "在长度为 n \rm nn 的字符串 w \rm ww 上进行如下计算 :
① 扫描整个带子上的字符串 , 查看 0 00 和 1 11 的顺序 , 所有的 0 00 必须在所有的 1 11 前面 ; 如果顺序错误 , 进入拒绝状态 ;
② 扫描整个带子 , 遇到一个 0 00 , 就划掉一个 1 11 ; 如果带子上存在 0 00 和 1 11 , 该操作重复进行 ;
③ 如果最后只剩下 0 00 或只剩下 1 11 , 说明 两个数字的个数不等 , 进入拒绝状态 ; 如果最后带子上只剩下空白字符 , 说明两个数字个数相等 , 进入接受状态 ; "
分析上述算法的时间复杂度 :
字符串 w = " 0000 ⋯ 1111 ⋯ " \rm w = "0000 \cdots 1111 \cdots"w="0000⋯1111⋯" , 整个 字符串长度为 n \rm nn ;
① 首先从左向右扫描一遍字符串 , 如果 0 00 出现在 1 11 右边 , 说明字符串不符合条件 , 检查的字符个数最坏的情况就是遍历 n \rm nn 次 , 使用 大 O \rm OO 标记 为 : O ( n ) \rm O(n)O(n) ;
② 扫描带子 , 读取到一个 0 00 , 划掉一个 1 11 , 然后在掉过头来 , 读取到一个 0 00 , 划掉一个 1 11 ;
这是一个循环 , 计算循环复杂度 , 只需要考虑 每次循环花费的时间 , 和 循环次数 ;
循环的次数最坏情况是 n 2 \rm \cfrac{n}{2}
2
n
, 还是 n \rm nn 的数量级 , 标记为 O ( n ) \rm O(n)O(n) ;
每次循环的花费时间步数 : 向右走 n 2 \rm \cfrac{n}{2}
2
n
步 , 找到 1 11 字符 , 删除 1 11 字符后 , 然后再向左 n 2 \rm \cfrac{n}{2}
2
n
步 回到第 0 00 个 , 大约是 n 2 \rm \cfrac{n}{2}
2
n
步 , 数量级还是 n nn , 使用 大 O \rm OO 标记 为 : O ( n ) \rm O(n)O(n) ;
将上述 循环次数 和 每次循环步数 大 O \rm OO 标记 相乘 , 就是该阶段的 大 O \rm OO 标记 为 : O ( n ) × O ( n ) = O ( n 2 ) \rm O(n) \times O(n) = O(n^2)O(n)×O(n)=O(n
2
) ;
上述 ① 和 ② 总的 大 O \rm OO 标记 为 : O ( n ) + O ( n 2 ) = O ( n 2 ) \rm O(n) + O(n^2) = O(n^2)O(n)+O(n
2
)=O(n
2
)
