篇章一 数据结构——前置知识（一）

目录

1.集合框架

1.1 什么是集合框架

1.2 类和接口总览图

1.3 和集合类相关的工具

1.迭代器 

2.对象比较

3.工具类

2.时间和空间复杂度

2.1 时间复杂度

1.什么是时间复杂度

2.如何算时间复杂度

3.练习

3.1 计算bubbleSort的时间复杂度

3.2 计算binarySearch的时间复杂度

3.3 计算阶乘递归factorial的时间复杂度

3.4 计算斐波那契递归fibonacci的时间复杂度

2.2 空间复杂度

---

1.集合框架

1.1 什么是集合框架

Java集合框架 （Java Collection Framework） ，又被称为容器（Container），是定义在 java.util 包下的一组接口（Interface）和其实现类。

可以简单理解为：Java当中已经实现好的一些集合类【一些已经用Java实现好的数据结构】      

什么是数据结构：数据 + 结构 -> 是用来描述和组织一组数据的方式。

其主要表现为将多个元素 element 置于一个单元中，用于对这些元素进行快速、便捷的存储 store 、检索 retrieve 、管理 manipulate ，即平时我们俗称的增删查改 CRUD 。例如，一副扑克牌(一组牌的集合)、一个邮箱(一组邮件的集合)、一个通讯录(一组姓名和电话的映射关系)等等。

1.2 类和接口总览图

为什么要有如此多的集合类？（或者说为什么要有如此多的数据结构）

因为我们组织数据和描述数据的方式不一样，在特定的情况下，我们可能用链表组织数据，也有可能用哈希表组织数据，每一种集合类（数据结构），用到的场景不一样。所以创造了如此多的集合类（数据结构）。

1.3 和集合类相关的工具

1.迭代器 

Iterator

ListIterator

2.对象比较

Comparable

Comparator

3.工具类

Arrays

Collections

这些工具的运用在后面的文章中涉及到，会讲解。

2.时间和空间复杂度

下面求斐波那契数列的算法好还是不好，为什么？该如何衡量一个算法的好坏呢？

public static long Fib(int N){if(N < 3){return 1;}return Fib(N-1) + Fib(N-2);
}

2.1 时间复杂度

1.什么是时间复杂度

在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。

简单来说：算法中的基本操作的执行次数，为算法的时间复杂度。

2.如何算时间复杂度

3.练习

求复杂度 一定要结合算法思想

3.1 计算bubbleSort的时间复杂度

3.2 计算binarySearch的时间复杂度

3.3 计算阶乘递归factorial的时间复杂度

3.4 计算斐波那契递归fibonacci的时间复杂度

2.2 空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

因为现在看的是程序的时间复杂度（也就是快不快），还支持牺牲空间来换取时间，所以这里就不再深入阐述了。