算法的概念.md

实际问题在计算机实现的五个步骤

---

算法分析

算法复杂度分析

1. 时间复杂度
2. 空间复杂度

• N 算法要解决问题的规模
• I 算法的输入
• A 算法本身的函数

C 表示复杂性 C = F(N,I,A)

1. 时间复杂度 T(N,I)
2. 空间复杂的 S(N,I)

如何将复杂度函数 F 具体化？

I 不考虑输入

• 设此抽象的计算机所提供的元运算有 k 种,分别记为O1,O2,...Ok
• 又设每次执行一次这些元运算的时间分别为t1,...t2
• 对于算法 A ,设统计用到元运算Oi 的次数 ei

ei=ei(N,I) 因此

一个算法用程序设计语言表示后,算法就是由一组语句构成,算法的执行效率就由各语句执行次数所决定

计算步：

• 一个算法中的语句执行次数称为语句频度或时间频度。T(n)

• 一般情况下,算法的基本操作重复执行的次数是模块 n 的某一个函数 f(n) ,因此,算法的时间复杂度记做: T(n) = O (f(n))

• 分析: f(n) 越小,算法的时间复杂度越低,算法的效率越高.

---

I 考虑输入

1. 最佳情况
   • 时间最快
2. 最坏情况
   • 时间最长
3. 平均情况

---

渐进表达式

渐进分析

可以采用渐近复杂性分析代替数学分析来比较算法效率 书上

---

• 多项式:时间复杂度不超过最高次或者等于最高次

• 对数:对数的底 跟时间复杂度没关系
• 对数时间复杂度一定低于次方时间复杂度
• 指数:次方时间复杂度一定低于指数时间复杂度