如何分析数据结构与算法中的时间与空间复杂度指标

   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).