数据结构之算法和算法分析[5]

⒉空间复杂度

一个程序的空间复杂度(Space complexity)是指程序运行从开始到结束所需的存储量

程序的一次运行是针对所求解的问题的某一特定实例而言的例如求解排序问题的排序算法的每次执行是对一组特定个数的元素进行排序对该组元素的排序是排序问题的一个实例元素个数可视为该实例的特征

程序运行所需的存储空间包括以下两部分

⑴固定部分这部分空间与所处理数据的大小和个数无关或者称与问题的实例的特征无关主要包括程序代码常量简单变量定长成分的结构变量所占的空间

⑵可变部分这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关例如个数据元素的排序算法与个数据元素的排序算法所需的存储空间显然是不同的

[] [] [] [] []