3分钟速读原著《Java数据结构与算法》(一)

第一章 综述

1.基本数据结构的优缺点

2.Java和C++的基本区别

• 2.1 Java中没有指针的概念

• 2.2.本质上Java中的存储地址就是相当于C++当中的指针的概念==>可以说Java中的一切引用类型都类似于C++当中的指针的概念

3.小结

• 3.1.数据结构是指针数据在计算机内存空间中或磁盘当中的组织形式

• 3.2.正确的选择数据结构会使得程序的效率大大提高

• 3.3.算法是完成特定任务的过程

• 3.4.在java中,算法经常通过类的方法来实现的

• 3.5.数据库是指由许多类似记录组成的数据存储的集合额

第二章 数组

1. 无序数组

• 有索引时直接根据索引查找

• 无索引时根据值查找,使用线性查找

2. 有序数组

• 2.1 二分查找法

所需次数比较如下图

• 2.2．如果查找的范围是2的幂,那么跟次数的比较刚好是一个对数log2®,如下图

• 2.3 大O表示法

举例说明:汽车按照尺寸可以分为微型,小型,中型等等.在不提及具体尺寸的情况下,这些分类可以为我们所涉及到的车的大小提供了一个大致的概念.我们同样也需要一种快捷的方法来评价计算机算法的效率.在计算机科学当中,这种粗略的度量方式就被称为大O表示法

3.小结

• 3.1 Java中数组是对象,由new操作创建
• 3.2 无序数组可以提供快速的插入,但查找和删除比较慢
• 3.3 将数组封装到类当中可以保护数组不被随意更改
• 3.4 有序数组可以使用二分查找
• 3.5 线性查找需要的时间与数组中数据项的个数成正比
• 3.6 二分查找需要的时间与数组中数据项的个数的对数成正比
• 3.7 大O表示法为比较算法的速度提供了一种方便的方法