《数据结构》学习笔记二:算法(二)
继续上节的学习,我们在这一篇文章里把“算法”这一章内容学习完。
本节处理问题:
算法的好坏究竟是如何评估的?
知识点:
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 = 100while i < n3 { i = i * 2}print("i = \(i)")这个循环的复杂度是 O(logn)。
image.png
4》平方阶
let x = 10, y = 10for 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所占存储空间的函数。
通常,我们都是用“时间复杂度”来指运行时间的需求,使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时,通常是指时间复杂度。
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 《数据结构》学习笔记二:算法(二)