网站建设先进工作者,沪深互动平台,2019银川住房建设规划信息网站,wordpress模板文件是哪个文件夹学习的目的 数据结构与算法的重要性#xff0c;对于大部分刚接触工作的程序员而言#xff0c;好像并没有什么太大的感触#xff0c;其中也包括我。因为在刚开始的工作中#xff0c;并不会用到什么复杂的数据结构和算法。也能完成我们工作中的需求。 但是人总是要有追求的对于大部分刚接触工作的程序员而言好像并没有什么太大的感触其中也包括我。因为在刚开始的工作中并不会用到什么复杂的数据结构和算法。也能完成我们工作中的需求。 但是人总是要有追求的一味的游走于皮毛之处那你一直都无法得到进步的。都说数据结构和算法是程序员的内功修炼好内功就可以走遍天下都不怕。为了更好的职业发展以及对待程序员这份职业的追求我觉得还是很有必要系统的学习数据结构和算法。 并且在拥有良好的思维习惯之后学习数据结构和算法的过程非常锻炼自己的思维能力我相信在写代码的时候我们会潜移默化的考虑到代码的效率问题优秀工程师与一般工程师的区别。帮助我们写出更好的代码。在进行代码优化的时候也能提出自己独到的见解 在这个专栏中我会把我学习到的记录下来并分享给他人。也算是对自己的一种激励。
什么是复杂度 我们知道数据结构和算法的作用就是帮助你写出执行效率更高更省资源的代码。但是我们如何去评价一份代码的优劣呢 有朋友说我们可以通过运行代码查看程序的执行时间和占用资源来评价一个代码的好坏。没错这样的方式的确没错。但是却有很大的局限性。这种方式被称作为事后统计法。
局限性
非常依赖测试环境
比如同样的代码分别运行在i3和i9的电脑上不用说两者的消耗的时间肯定是不一样的。 2. 受数据规模的影响 很多的算法是针对大量数据进行使用的在测试的时候我们一般很难满足这样大数据量的需求。
需要完成代码的编写才能进行验证 事后统计法需要我们完成代码的编写才能进行测试。这样的效率也是比较低的 由上可知事后统计法并不能用于评价代码的优劣。那么什么方法可以方便的评价代码的优劣呢可以在我们编写代码之前就可以分析出來即使进行改善。
这就是复杂度的概念了。在数据结构和算法中我们统一用复杂度来评价代码的执行效率。
复杂度分为时间复杂度和空间复杂度。
时间复杂度
时间复杂度表示代码执行时间随数据规模增长的变化趋势。切记这是一个趋势并不是准确的值。
我们常常使用大O表示法来表示复杂度T(n) O(f(n))
T(n),表示代码的执行时间f(n),表示代码的执行次数O表示代码执行一次所用时间关系。
比如下面的代码 int cal(int n) { int sum 0; int i 1; int j 1; for (; i n; i) { j 1; for (; j n; j) { sum sum i * j; } } } 我们知道总共需要执行代码次数为2n^2 2n3。大O表示法只保留最高次项。故该代码的时间复杂度为T(n)O(n^2)
如何分析时间的复杂度
一段代码该怎么分析呢一般从以下三步入手
1. 只关注循环次数执行最多的一段代码
在复杂度介绍中我们说过时间复杂度只是表示执行时间随数据规模变化的一种趋势。并且大O表示法中会忽略公式中低介常量系数。因此对于一段代码中我们只关注循环次数最多的一段代码即可。其它的可以忽略。 例如 int cal(int n) { int sum 0; int i 1; for (; i n; i) { sum sum i; } return sum; }
在上面的代码中我们只需要关注for循环中的代码其它单行指令可以忽略。它的时间复杂度为O(n)。
2. 加法法则。总复杂度等于量级最大的那段代码的复杂度 int cal(int n) { int sum_1 0; int p 1; for (; p 100; p) { sum_1 sum_1 p; } int sum_2 0; int q 1; for (; q n; q) { sum_2 sum_2 q; } int sum_3 0; int i 1; int j 1; for (; i n; i) { j 1; for (; j n; j) { sum_3 sum_3 i * j; } } return sum_1 sum_2 sum_3; } 在上面的代码中我们可以看到由三个循环体时间复杂度分别是O(1),O(n),O(n^2) 。总的时间复杂度就是最大量级的那段代码的复杂度。O(n^2)。 如果复杂度分别是O(f(n)),O(g(n))。那么T(n)max(O(f(n)),O(g(n)))
3. 乘法法则。嵌套代码的复杂度等于嵌套代码复杂度的乘积 int cal(int n) { int ret 0; int i 1; for (; i n; i) { ret ret f(i); } } int f(int n) { int sum 0; int i 1; for (; i n; i) { sum sum i; } return sum; }
由加法法则可知我们乘法法则的的公式应该为T(n)O(f(n)*g(n))。
常见的时间复杂度
知道如何计算复杂度之后再介绍一下我们常见的复杂度量级。
常量介 O(1)对数阶 O(logn)线性介 O(n)线性对数阶 O(nlogn)平方介 O(n(2 ),O(n)3 ),O(n^k)指数介 O(2^n)阶乘介 O(n!) 有些刚接触的人对对数阶有疑惑包括我。比如我们通过计算得出两个代码的执行次数分别是以2为底数的对数一个是以10为底数的对数。其实差距也是挺大的。为什么统一写成logn呢 其实这是因为大O表示法可以去除系数而不同底数的对数都可以转换为同底数乘以一个系数。所以对数的底数也就没有什么意义了。所以统一不加上底数。
空间复杂度
空间复杂度和时间复杂度类似表示算法的储存空间于数据规模之间的增长关系。
这里比较简单了我也不再赘述了。常见的空间复杂度就是O(1),O(n),O(n^2)。
最好情况时间复杂度最坏情况时间复杂度
我们尝试分析下面代码的时间复杂度。 // n表示数组array的长度 int find(int[] array, int n, int x) { int i 0; int pos -1; for (; i n; i) { if (array[i] x) { pos i; break; } } return pos; } 由代码逻辑可知,该函数的目的是在长度为n的数组array中找到x,并返回其下标若不存在则返回-1。根据之前的分析方式能得出该代码的复杂度吗显然是不能的。 因为X在数组中的位置我们不确定他有可能就是第一个数for循环执行一遍就结束了。复杂度为O(1),但也有可能X不在数组中那么for循环就要执行n遍才能结束。因此复杂度为O(n)。 这两种情况就是最好情况时间复杂度最坏情况时间复杂度。
顾名思义 最好情况时间复杂度就是在最理想的情况下执行这段代码的时间复杂度最坏情况时间复杂度就是在最糟糕的情况下执行这段代码的时间复杂度。
平均时间复杂度 我们知道最好情况时间复杂度和最坏情况时间复杂度都是对应极端情况下的代码复杂度。发生的概率并不大为了更好的表示平均环境下的复杂度我们需要引入平均时间复杂度的概念。 平均时间复杂度分析还是比较麻烦的继续根据上面的代码进行分析 变量X的位置有两种情况在数组中和不在数组中。为了简单起见假设在数组中的概率和不在数组中的概率分别为二分之一。在数组中的位置有n种情况0~n-1。每一个概率都是相同的。故平均的T(n)n/2(1/2n2/2n3/2n...n/2n)(3n1)/4。即O(n).
均摊时间复杂度 均摊时间复杂度的计算较为复杂我这里就不再介绍了。容易把自己绕晕
但是什么时候需要用到均摊时间复杂度呢(直接从网上摘抄下来)。 对一个数据结构进行一组连续操作中大部分情况下时间复杂度都很低只有个别情况下时间复杂度比较高而且这些操作之间存在前后连贯的时序关系这个时候我们就可以将这一组操作放在一块儿分析看是否能将较高时间复杂度那次操作的耗时平摊到其他那些时间复杂度比较低的操作上。而且在能够应用均摊时间复杂度分析的场合一般均摊时间复杂度就等于最好情况时间复杂度。
总结 该篇主要介绍我们为什么需要学习数据结构与算法为了更好的未来发展以及对自己岗位的更高要求。数据结构与算法起始就是一种经验由前人总结。针对某一类问题使用某一个数据结构会十分方便。也介绍了如何判断代码优劣的方法复杂度。
但是我需要更正一点复杂度是一定的吗比如O(logn)一定比O(n)要高效吗 答案是否定的因为具体的还是要结合我们实际的环境这些复杂度是用于大数据规模的环境下得出来的参考表达式。但是如果我们的数据量比较小就不一定适用了。所以尽量结合自己的环境进行编码不要为了用某一个算法而写算法。
