初识数据结构

目录

1. 集合的框架

集合框架的重要性

数据结构的介绍

算法的介绍

容器背后对应的数据结构

2. 时间复杂度和空间复杂度

算法效率

时间复杂度

时间复杂度的概念

大O的渐进表示法

常见的时间复杂度的计算

空间复杂度

空间复杂度的概念

---

从本章开始又要开始新的篇章，本篇章称之为数据结构。我们的数据结构不同于那些课本上的数据结构；我们Java的数据结构将和集合结合在一起，我们从集合的底层开始学起，在“集合的框架”中会将整个知识体系串联起来。另外在本章将补充几个JavaSE的几个知识点。

1. 集合的框架

官方教程：Trail: Collections (The Java™ Tutorials) (oracle.com)https://docs.oracle.com/javase/tutorial/collections/index.html

思维导图：

集合框架的重要性

使用成熟的集合框架，有助于我们便捷、快速的写出高效、稳定的代码。

数据结构的介绍

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

算法的介绍

算法(algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

容器背后对应的数据结构

我们主要学习以下容器，每个容器其实都是对某种特定数据结构的封装，大概了解一下，后序会给大家详细讲解并模拟实现

1. Collection：是一个接口，包含了大部分容器常用的一些方法
2. List：是一个接口，规范了ArrayList 和 LinkedList中要实现的方法
ArrayList：实现了List接口，底层为动态类型顺序表
LinkedList：实现了List接口，底层为双向链表
3. Stack：底层是栈，栈是一种特殊的顺序表
4. Queue：底层是队列，队列是一种特殊的顺序表
5. Deque：是一个接口
6. Set：集合，是一个接口，里面放置的是K模型
HashSet：底层为哈希桶，查询的时间复杂度为O(1)
TreeSet：底层为红黑树，查询的时间复杂度为O( ),关于key有序的
7. Map：映射，里面存储的是K-V模型的键值对
HashMap：底层为哈希桶，查询时间复杂度为O(1)
TreeMap：底层为红黑树，查询的时间复杂度为O( )，关于key有序

2. 时间复杂度和空间复杂度

对于同一个问题，有无数种解决方法，那么哪一种解决方法才算是好方法呢？

同样的，同一个问题，有无数种算法，哪一种算法才是好算法？

于是提出了：算法效率

算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。

经过多年的发展，我们内存选择已经非常大了，而且相对便宜，我们已经不再那么的关注空间效率了，大多数时候都是以空间换取时间。

时间复杂度

时间复杂度的概念

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。——百度百科

一个算法所消耗的时间，理论上来说不能直接计算，需要在机器跑起来以后才知道；但是我们所有的算法都需要跑一次吗？确实可以每个算法都运行一遍，但是这无疑会造成误差，例如：每个人的机器不同，可能网络造成的延迟，可能内部零件影响，这都可以造成误差。于是我们规定：一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

大O的渐进表示法

算法的时间复杂度通常用大O符号表述，定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。 如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。

举例：

 public static void main(String[] args) {
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                count++;
            }
        }
        for (int i = 0; i < 100; i++) {
            count++;
        }
        count++;
    }

问：改代码的时间复杂度是多少？

根据数学算法： O（N）= N^2 + N + 1

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1.  用常数1取代运行时间中的所有加法常数

O（N）= N^2 + N 

2. 只保留最高阶项

O（N）= N^2

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。 使用大O的渐进表示法以后，该算法的时间复杂度为：

O（N）= N^2

假设算法的N无限大，那么对于最高阶项而言，其他项、常数和系数都不那么重要了。

 public int Function(int n, int x){
        int sum = 0;
        for (int i = 1; i <= n; ++i) {
            if (i == x) 
                break;
            sum += i;
        }
        return sum;
 }

重点分析循环这一段代码，这段代码根据x值的不同，时间复杂度也有区别：

1.当x>n时，此代码的时间复杂度是O(n)。

2.当1<=x<=n时，时间复杂度是一个我们不确定的值，取决于x的值。

3.当x=1时，时间复杂度是O(1)。

这段代码在不同情况下，其时间复杂度是不一样的。所以为了描述代码在不同情况下的不同时间复杂度，我们引入了最好、最坏、平均时间复杂度。

1.最好情况时间复杂度

当我们一次就找到了我们想要的结果。

2..最坏情况时间复杂度

上述示例就是n

最好、最坏都是在对应的都是极端情况下的代码复杂度，发生的概率其实并不大。
其中最好、最坏情况下的时间复杂度分析起来比较简单

3..平均时间复杂度

分析上面的示例代码，判断x在循环中出现的位置，有n+1种情况：1<=x<=n 和n 我们将所有情况下代码执行的次数累加起来（（1+2+3…+n）+n），然后再除以所有情况数量（n+1），就可以得到需要遍历次数的平均值。

可以参考这个公式，P表示出现的概率，n表示问题规模。 

常见的时间复杂度的计算

举例：

1. O（N）

for (int j = 0; j < N; j++) {
                count++;
            }

2. O（N^2）

for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                count++;
            }
        }

3. O（N^3）

在双重嵌套的情况下再加一层for循环，以此类推。

4. O（log2 N）

log2 其中的2是底数，为了避免歧义后面画图解释。

 int i = 1;
        while (i < N) {
            i *= 2;
        }

5. 线性对数阶O（nlog2n）

for (int j = 0; j < m; j++) {
            int i = 1;
            while (i < N) {
                i *= 2;
            }
        }

6.立方阶O（n³）

7.k次方阶O（n的k次方）

8.指数阶O（2的n次方）

空间复杂度

我们再此不做过多介绍，现在的空间复杂度并非最重要的，我们现在更在乎的是时间的效率。

空间复杂度的概念

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

分析原则：时间复杂度关注代码的执行次数，而空间复杂度主要关注申请空间的数量。