算法及其性质
算法是对问题求解过程的准确描述，由有限条指令组成，这些指令能在有限时间内执行完毕并产生确定性的输出。
性质：
1、输入：零个或多个外部量输入
2、输出：至少产生一个量作为输出，输入输出存在联系
3、确定性：组成算法的每条指令都是清晰、无歧义的。
4、有限性：每条指令的执行次数有限，执行每条指令的时间也有限。
算法复杂度
复杂度：算法运行时需要耗费计算机资源的量，可以分为时间复杂度和空间复杂度。
复杂度依赖三个方面：待求解问题规模，算法的输入、算法本身。
元运算：不管使用什么样的算法和输入数据，该运算的上阶是一个常数时间。
四种阶
O
- 定义：如果存在正的常数C和自然数n0，使得当
n≥n0时， 有f(n)≤C·g(n)，则称函数f (n) 在n 充分大
时有上有界，且g(n) 是它的一个上界，记做f (n) =
O(g(n)) ，并称f (n) 的阶不高于g(n) 的阶。 - 上界的阶越低，评估越有价值
- 阶运算时，常系数、低阶以及常数项可以忽略
- 定义：如果存在正的常数C 和自然数n0 ， 使得
当n ≥ n0时， 有f(n)≥C·g(n)，则称函数f (n) 在n 充分
大时有下有界，且g(n) 是它的一个下界，记做f (n) =
Ω(g(n)) ，并称f (n) 的阶不低于g(n) 的阶。 - 下阶越高，评估精度越高
Θ
- 定义：f (n) = Θ(g(n)) ，当且仅当f (n) =
O(g(n)) ，且f (n) = Ω(g(n)) ，称f (n) 和g(n) 是同阶。
o
-
定义：对于任意给定的ε > 0 ，存在正整数n0 ，
使得当n ≥ n0 时，有f (n) / g(n) ≤ε ，则称函数f (n)
在n 充分大时的阶比g(n) 低，记为f (n) = o(g(n)) 。
阶.png
计算时间复杂度
计算迭代次数
- 使用计算迭代次数的技术来分析算法的时间复杂度时，只需要考虑
最深层次的迭代。 -
常见查找、排序
计算迭代次数.png
使用递归方程
使用频度分析
算法复杂度分析意义
- 已知待求解问题的多种算法时，挑选复杂度尽可能低
的算法进行应用。 - 给定待求解的问题，设计复杂度尽可能低的算法。
- 设计出算法后，不要急于实现，而是先进行复杂度分
析后；若该算法确实可行，才有实现的价值与必要
