继续上节的学习，我们在这一篇文章里把“算法”这一章内容学习完。
本节解决问题：
算法的好坏到底是如何评估的？
知识点：
1.函数的渐进增长
2.算法的时间复杂度
3.常见的时间复杂度
4.算法的空间复杂度
1.函数的渐进增长
这一知识点与数学相关，不过没关系都是很容易理解的内容。
问题： 假如两个算法的输入规模都是n, A的执行次数是 2n +3, B 的执行次数是 3n + 1,那么这两个算法哪一个更好呢？
我们来分析一下，用数学的折线图更够很直观的看到了。
image.png
这里先给出渐近增长的概念。
输入规模n在没有限制的情况下，只要超过一个数值N，这个函数就总是大于另一个函数，我们称函数是渐近增长的。
函数的渐近增长： 给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n) > g(n),那么我们就说f(n)的渐近增长快于g(n)。
从图中可以看出，随着n的增大，后面的 +3, 和 +1 对结果的影响并不大。同样的，与最高次项相乘的的常数也不是很重要。
我们再看一个例子：
算法 C是 2n^2, D是n^2 + 3n ,我们在来看看他们的曲线图。
image.png
从图中可以看出，最高次项的指数大的，函数随着n的增长，结果也会变得增长的特别快。
于是我们总结出，判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更加关注主要项（最高阶项）的阶数。
2. 算法的时间复杂度
定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n变化的情况并确定T(n)的数量级。记做： T(n) = O(f(n))。
这样用大写的O（）来提现算法时间复杂度的记法，我们称为大O记法。一般情况下，T(n)增长的最慢的就是最优算法。
推导大O阶的方法：
- 用常数 1 取代所有的加法常数；
- 在修改后的函数中，只保留最高阶项；
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数，得到的结果就是最终的大O阶。
例如：
image.png
下面我们看几个常见的时间复杂度。
1》常数阶
执行的次数与n无关，这样的时间复杂度就是常数阶，根据大O阶的记法，记做O(1) 。
注意： 不管这个常数是多少，我们都记做O(1), 而不是 O(3), O(12)等。
2》 线性阶（ O(n) ）
线性阶的循环结构要复杂的多。分析算法的复杂度，关键是要分析循环结构的运行情况。
3》 对数阶
例如：
var i = 1, n3 = 100
while i < n3 {
i = i * 2
}
print("i = \(i)")
这个循环的复杂度是 O(logn)。
image.png
4》平方阶
let x = 10, y = 10
for i in 0..<x {
for i in 0..<y {
print("hello")
}
}
时间复杂度为 O(n^2) 。
3. 常见的时间复杂度
111.jpg
4. 算法的空间复杂度
算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记做： S(n) = O(f(n)) 。
n:问题的规模（输入）
f(n): 关于n所占存储空间的函数。
通常，我们都是用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时，通常是指时间复杂度。
网友评论