如何分析数据结构与算法中的时间与空间复杂度指标
今天给大家介绍一下如何分析数据结构与算法中的时间与空间复杂度指标。文章的内容小编觉得不错，现在给大家分享一下，觉得有需要的朋友可以了解一下，希望对大家有所帮助，下面跟着小编的思路一起来阅读吧。
下面主要是对底层的数据结构与算法部分进行详尽的讲解，侧重的是度量的几个维度。
1.最好、最坏情况时间复杂度
最好情况时间复杂度就是，在最理想的情况下，执行一段代码的时间复杂度。比如一个数组其中有10个元素，我们要找一个元素，当要查找的元素正好是这个数组的第一个元素，这个时候对应的时间复杂度就是最好情况下的时间复杂度。
最坏情况时间复杂度就是，在最糟糕的情况下，执行一段代码的时间复杂度。正如上面的例子，若要找的这个元素不在这个列表中或者在最后的一个位置，则我们就需要把整个数组遍历一遍才行，所以这种最糟糕情况下对应的时间复杂度就是最坏情况复杂度。
2.平均情况时间复杂度
我们从上面的第一条中可以感知，最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实并不大。为了更好表示平均情况下的复杂度，我们需要引入另一个概念：平均情况下时间复杂度，我们简称平均时间复杂度。
我们就上面的例子分析一下平均情况下的时间复杂度，我们要查找的变量设为X,其在数组中的位置有n+1中情况：在数组的0~n-1位置中和不在数组中。我们把每种情况下需要查找的遍历的元素个数累加起来，然后再除以n+1，就可以得到需要遍历的元素个数的平均值，即:(1+2+3+.....+n+n)/(n+1)=n(n+3)/2(n+1)
我们通过上节知道，时间复杂度的大O标记法中，可以省略掉系数、低阶、常量，所以，化简后可得平均时间复杂度就是O(n).
以上就是如何分析数据结构与算法中的时间与空间复杂度指标的全部内容了，更多与如何分析数据结构与算法中的时间与空间复杂度指标相关的内容可以搜索之前的文章或者浏览下面的文章进行学习哈！相信小编会给大家增添更多知识,希望大家能够支持一下！
