数据结构复习资料-java数据结构期末考试

第二章 算法分析1.算法分析是计算机科学的基础2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用3.渐进复杂度：随着 n 的增加时增长函数的一般性质，这一特性基于该表达式的主项，即 n 增加时表达式中增长最快的那一项。4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。6.只有可运行的语句才会增加时间复杂度。7. O() 或者 大 O 记法：与问题大小无关、执行时间恒定的增长函数称为具有 O（1）的复杂度。增长函数阶次t(n)=17O(1)t(n)=3log nO(log n)t(n)=20n-4O(n)t(n)=12n log n + 100nO(n log n)t(n)=3 + 5n - 2O()t(n)=8 + 3O()t(n)=+ 18 +3nO()8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。9.假如算法的运行效率低，从长远来说，使用更快的处理器也无济于事。10.要分析循环运行，首先要确定该循环体的阶次 n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小）11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。12.方法调用的复杂度分析：如：public void printsum(int count){int sum = 0 ;for (int I = 1 ; I < count ; I++)sum += I ;System.out.println(sun); }printsum 方法的复杂度为 O（n）,计算调用该方法的初始循环的时间复杂度，只需把 printsum 方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的 printsum 方法的复杂度为 O（）。13 指数函数增长 > 幂函数增长 > 对数函数增长第三章 集合概述——栈1.集合是一种聚集、组织了其他对象的对象。它定义了一种特定的方式，可以访问、管理所包含的对象（称为该集合的元素）。集合的使用者——通常是软件系统中的另一个类或对象——只能通过这些预定的方式与该集合进行交互。2.集合可分为线性集合和非线性集合。线性集合是一种元素按直线方式组织的集合。非线性集合是一种元素按某种非直线方式组织的集合，例如按层次组织或按网状组织。从这种意义上来说，非线性集合也许根本就没有任何组织形式。3.集合中的元素通常是根据它们添加到集合的顺序，或者是按元素...