【算法】算法设计与分析 课程笔记 第一章&第二章

第一章 算法概述

算法的性质

算法的四个性质：输入、输出、确定性和有穷性。

算法的时间复杂度

1. 常见的时间复杂度

1. 常数阶 O(1)

2. 对数阶 O(log n)

3. 线性阶 O(n)

4. 线性对数阶 O(nlog n)

5. 平方阶 O(n^2)

6. 立方阶 O(n^3)

7. k 次方阶 O(n^k)

8. 指数阶 O(2^n)

注：上面的 log n 均代表以2为底的对数。

2. 时间复杂度排序

常见的算法时间复杂度由小到大依次为：

Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜Ο(n^2)＜Ο(n^3)＜ Ο(n^k) ＜ Ο(2^n)

 随着问题规模n的不断增大，上面时间复杂度的值也不断增大，算法的执行效率越来越低。

PTA习题选讲

单选题

虽然没难度，但是考了各种复杂度的排序，警醒我需要把那一串背下来！

O（1）< O（log n）< O（n）< O（nlog n）< O（n^2）< O（n^3）

灵机一动，直接用2代入也可以！其实就是考函数的大小罢了！

 填空题

假设某算法在输入规模为n时的计算时间为T(n)=3∗2^n。

在某台计算机上实现并完成该算法的时间为 t 秒。

现有另一台计算机，其运行速度为第一台的64倍，

那么在这台新机器上用同一算法在 t 秒内能解决问题的输入规模为（    ）。

如果算法计算时间改进为T(n)=n^2，其余条件不变，

则新机器上用 t 秒可以解决问题的输入规模为（   ）。

第一小问，因为两台机器的共同变量只有时间t，所以从t入手，

因为新机器的速度是旧机器的64倍，所以新机器用t秒时间解决的问题规模是旧机器的64倍，

∴可得：T’(n) = 64*T(n) = 64*3*2^n = 3*2^(n+6)

问题规模和输入规模是不同的概念，所以新机器的输入规模应该是 n+6 

第二小问，同理，只需要把上式的T(n)换为n^2：

T’(n) = 64*T(n) = 64*n^2 = (8*n)^2

故在这个条件下输入规模则为 8*n

课本习题选讲

1. 求下面式子的渐进表达式：

      21 + 1 / n

答案：O ( 1 ) 

解析：求渐进表达式，只需要将其中的n设置为无穷大即可，当这个式子里的n为无穷大时，整个式子趋近于常数，因此渐进表达式为常数阶 O ( n ) 。

解析：O是指上界，Ω是指下界，θ是指上下界相等，在这里，可以这样理解：

f(n) = O(g(n)) 意味着 g(n) 在 n 趋近于无穷大时比 f(n) 大；

f(n) = Ω(g(n)) 意味着 g(n) 在 n 趋近于无穷大时比 f(n) 小；

f(n) = θ(g(n)) 意味着 g(n) 在 n 趋近于无穷大时和 f(n) 同阶；

因此答案如下：

（1）θ （2）O （3）Ω （4）Ω

（5）θ （6）Ω （7）Ω （8）O