【数据结构】-时间复杂度和空间复杂度

在阅读这篇文章之前，建议大家先对【数据结构】-宏观认识进行阅读，对数据结构有一个宏观的了解。我们使用@H_404_2@时间复杂度和空间复杂度对算法进行分析。@H_404_2@

@H_404_2@

时间复杂度@H_404_2@

算法包含的计算量。@H_404_2@

大O表示法，表示时间复杂度，不考虑具体的运行时间，只给出算法在问题规模n的某个函数。@H_404_2@

时间复杂度常见的阶数有常数阶（算法的时间复杂度与输入规模n无关），对数阶，线性阶，多项式阶，指数阶。通常认为，时间复杂度具有指数阶的算法是实际不可计算的，阶数低于平方阶的算法是高效率的。@H_404_2@

@H_404_2@

一个算法对具有相同输入数据量的不同输入数据，时间复杂度可能会不同，使用最坏时间复杂度和平均时间复杂度来度量算法的性能。@H_404_2@

@H_404_2@

最坏时间复杂度：对相同输入数据量的不同输入数据，算法时间用量的最大值。@H_404_2@

平均时间复杂度：对所有相同输入数据量的各种不同输入数据，算法时间用量的平均值。@H_404_2@

@H_404_2@

空间复杂度是一个算法在运行过程中临时占用存储空间大小的度量。@H_404_2@

一个算法在执行期间所需要的存储空间量包括三个部分：@H_404_2@

程序代码所占用的空间@H_404_2@

输入数据所占用的空间@H_404_2@

辅助变量所占用的空间@H_404_2@

输入数据所占空间由问题决定，不随算法的不同而改变。@H_404_2@

程序代码所占空间对不同的算法也不会有数量级的差别。@H_404_2@

辅助变量所占空间由算法决定，有的占用随问题规模n增大而增大的临时空间，有的不随问题的规模改变。@H_404_2@

@H_404_2@

在估算算法空间复杂度时，只需要分析辅助变量所占用的空间。@H_404_2@

@H_404_2@

掌握时间复杂度和空间复杂度的分析重点。时间复杂度分析算法的计算量，而空间复杂度分析算法运行时占用的存储空间，主要是对辅助变量的分析。从这两个不同的角度对算法进行分析，设计高效率算法。@H_404_2@