试题详情
简答题什么是算法的渐近空间复杂度？如何分析一个算法的渐近空间复杂度？
  • 算法的渐近空间复杂度是对算法的空间效率的度量。也就是对一个算法执行所需要的存储空间进行分析。一个算法执行时所需要的空间包括几个方面，如存储程序指令所需要的空间，存储输入数据的空间等。与分析算法的时间复杂度类似，为了能够反映一个算法的空间性能，要排除与算法性能无关的存储空间需求，仅考虑算法执行时所需要的辅助存储空间，因为它直接与算法的空间性能有关。一个算法执行时所需要的辅助存储空间量也可以表示为问题规模n的函数，其大O表示称之为算法的渐近时间复杂度。也简称为算法的空间复杂度。
    根据上述概念，分析算法的渐近空间复杂度就是要考察和分析算法执行时所需要的临时工作单元、动态使用的空间、递归工作栈所占空间等辅助空间的需求量，然后将其表示为问题规模的函数，也就是用大O表示法表示它，即可得到算法的渐近空间复杂度。

  • 关注下方微信公众号，在线模考后查看

热门试题