【数据结构】(2)时间、空间复杂度

一、衡量算法好坏的指标

        时间复杂度衡量算法的运行速度，空间复杂度衡量算法所需的额外空间。这些指标，是某场景中选择使用哪种数据结构和算法的依据。如今，计算机的存储器已经变得容易获得，所以不再太关注空间复杂度。

二、渐进表示

        复杂度是一个渐进表示，它不代表算法的运行速度或者利用的额外空间的实际值，而是代表它们与数据规模 N （输入到算法中的数据量）相关的变化趋势。因此，复杂度更高的，并不代表实际的运行时间更长，实际运行时间由数据规模、算法复杂度、计算机的硬件性能共同决定。

        不同规模的时间复杂度比较：

        1 < logn < n < nlogn < n^2 < n^3 < 2^n < n! < n^n

三、最好、平均、最坏复杂度

• 最好：最好情况下的复杂度。
• 最坏：最坏情况下的复杂度，最常考虑的。（只要考虑了最坏情况，所有情况都没问题了）
• 平均：所有情况(发生的概率x执行次数)之和。

四、时间复杂度的计算

        关键是，计算出算法的基本操作（比如：算术计算、比较等）的执行次数。其次，只取最高次项，并去掉系数。为什么要去掉系数、非最高项？比如一个算法的基础操作执行次数是 N^2 + N，若 N=1,0000，结果为 1,0001,0000，这时 1,0000 相对于 1,0001,0000 就是一个很小的数目，对结果没有多大影响，可以忽略。

1、例1

T(n) = O(n^2)

2、例2

T(n) = O(1)

3、例3

T(n) = O(n^2)

        直接写3个赋值语句和调用函数在执行效率上有差别，但是我们不需要深究。实际上在编译时，Swap 函数调用会被直接替换成3个赋值语句，因为在 java 中存在 inline 体系，编译器会自动识别哪些方法应该进行 inline 操作，这样的目的就是提高执行效率。

4、例4

T(n) = O(logn)，注：省略底的log默认底为2。

5、例5

T(n) = O(2^n)，数据规模稍微大点，执行效率将非常慢。 

五、空间复杂度

        注意，空间复杂度是执行算法所需要的额外空间，所以进入算法前已经消耗的空间是不算数的。

1、例1

T(n) = O(1)

2、例2

T(n) = O(n)

3、例3

T(n) = O(n)