09年自考《数据结构》各章要点一[2]

抽象数据类型ADT

·是抽象数据的组织和与之的操作相当于在概念层上描述问题

·优点是将数据和操作封装在一起实现了信息隐藏

程序设计的实质是对实际问题选择一种好的数据结构设计一个好的算法算法取决于数据结构

算法是一个良定义的计算过程以一个或多个值输入并以一个或多个值输出

评价算法的好坏的因素

·算法是正确的

·执行算法的时间

·执行算法的存储空间(主要是辅助存储空间)

·算法易于理解编码调试

时间复杂度是某个算法的时间耗费它是该算法所求解问题规模n的函数

渐近时间复杂度是指当问题规模趋向无穷大时该算法时间复杂度的数量级

评价一个算法的时间性能时主要标准就是算法的渐近时间复杂度

算法中语句的频度不仅与问题规模有关还与输入实例中各元素的取值相关

时间复杂度按数量级递增排列依次为常数阶O()对数阶O(logn)线性阶O(n)线性对数阶O(nlogn)平方阶O(n^)立方阶O(n^)……k次方阶O(n^k)指数阶O(^n)

空间复杂度是某个算法的空间耗费它是该算法所求解问题规模n的函数

算法的时间复杂度和空间复杂度合称算法复杂度

[] [] [] [] [] [] [] [] [] [] []