数据结构--准备知识

一.算法效率算法效率分为两种第一种为时间效率第二种为空间效率。时间效率称为时间复杂度空间效率称为空间复杂度。时间复杂主要衡量一个算法的运行速度空间复杂度主要衡量一个算法所需的额外的空间现在不需要特别关注现在的磁盘空间特别大。二.时间复杂度1.概念算法中基本操作的执行次数为算法的复杂度2.大O的渐进表示法算法复杂度存在最好、平均、最坏情况最坏情况:任意输入规模的最大运行次数(上界)平均情况:任意输入规模的期望运行次数最好情况:任意输入规模的最小运行次数(下界)例如: 在一个长度为N数组中搜索一个数据x最好情况:1次找到最坏情况:N次找到平均情况:N/2次找到在实际情况中我们并不需要精确的执行次数一般关注最坏情况用大O的渐进表示法表示大O的渐进表示法规则1、用常数1取代运行时间中的所有加法常数2、在修改后的运行次数函数中只保留最高阶项。3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。举例三.空间复杂度空间复杂度是算法在运行过程中临时占用存储空间大小即新增变量的个数。也使用大O的渐进表示法举例四.包装类Java最开始讲过再Java中由于基本类型不是继承于Object类为了在泛型代码中支持基本类型所以个每个基本类型都对应一个基本类型1.装箱和拆箱装箱将基本类型变为包装类型的过程,分为自动装箱和显示装箱拆箱将包装类型变为基本类型的过程分为自动拆箱和显示拆箱举例注意五.泛型概念从代码上讲就是对类型实现了参数化主要目的就是指定当前的容器要持有什么类型的对象。让编译器去做检查。此时就需要把类型作为参数传递。需要什么类型就传入什么类型。语法利用Object举例利用泛型举例六.泛型的上界语法·举例接口也是如此七.泛型方法语法举例八.擦除机制概念在编译的过程中将所有的泛型类型T替换成他的上界类型默认为Object