【计算理论】计算复杂性 ( 小 O 记号 | 严格渐进上界 | 分析算法的时间复杂度 )

文章目录

• 一、小 O 记号 ( 严格渐进上界 )
• 二、分析算法的时间复杂度

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

---

如果

\rm g(n)

是

\rm f(n)

渐进上界 , 符号化表示为

\rm f(n) = O(g(n))

,

如果

\rm f(n)

除以

\rm g(n)

, 求

n \to \infty

极限为

0

时 , 符号化表示为

\rm lim_{n \to \infty} \cfrac{f(n)}{g(n)} = 0

,

那么称

\rm g(n)

是

\rm f(n)

的 严格渐进上界 ;

严格渐进上界使用 小

\rm o

记号 表示 :

①

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

②

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

③

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

④

\rm n\ log \ n = o(n ^2)

⑤

\rm n ^2 = o(n ^3)

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

---

构造图灵机认识如下语言 :

\rm A = \{ 0^k1^k : k \geq 0 \}

\rm M_1 =

"在长度为

\rm n

的字符串

\rm w

上进行如下计算 :

① 扫描整个带子上的字符串 , 查看

0

和

1

的顺序 , 所有的

0

必须在所有的

1

前面 ; 如果顺序错误 , 进入拒绝状态 ;

② 扫描整个带子 , 遇到一个

0

, 就划掉一个

1

; 如果带子上存在

0

和

1

, 该操作重复进行 ;

③ 如果最后只剩下

0

或只剩下

1

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

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

字符串

\rm w = "0000 \cdots 1111 \cdots"

, 整个 字符串长度为

\rm n

;

① 首先从左向右扫描一遍字符串 , 如果

0

出现在

1

右边 , 说明字符串不符合条件 , 检查的字符个数最坏的情况就是遍历

\rm n

次 , 使用 大

\rm O

标记 为 :

\rm O(n)

;

② 扫描带子 , 读取到一个

0

, 划掉一个

1

, 然后在掉过头来 , 读取到一个

0

, 划掉一个

1

;

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

循环的次数最坏情况是

\rm \cfrac{n}{2}

, 还是

\rm n

的数量级 , 标记为

\rm O(n)

;

每次循环的花费时间步数 : 向右走

\rm \cfrac{n}{2}

步 , 找到

1

字符 , 删除

1

字符后 , 然后再向左

\rm \cfrac{n}{2}

步 回到第

0

个 , 大约是

\rm \cfrac{n}{2}

步 , 数量级还是

n

, 使用 大

\rm O

标记 为 :

\rm O(n)

;

将上述 循环次数 和 每次循环步数 大

\rm O

标记 相乘 , 就是该阶段的 大

\rm O

标记 为 :

\rm O(n) \times O(n) = O(n^2)

;

上述 ① 和 ② 总的 大

\rm O

标记 为 :

\rm O(n) + O(n^2) = O(n^2)