java架构师系列1-数据结构(1)基本概念

这是我架构师系列第一篇文章，也是我的开山之作吧，所以在今后的文章中，我觉得还是要以通俗的比较容易理解的话来阐述问题。想要后续系列的文章，关注我，我会持续发布（希望你不是那个只收藏不看的人）。

废话不多说，如果我们想要学好数据结构与算法，首先脑海中要时刻记住两个关键词汇，时间效率和空间效率。这个两个词汇贯穿了整个架构师知识体系。那什么是时间效率和空间效率呢？通俗的理解就是：我们使用两个不同的程序去解决同一个问题，时间短的说明时间效率高，消耗空间小的说明空间效率高。现在回到我们的数据结构题目上。

我们在研究数据结构与算法的时候，其实就是在使用不同的数据结构和不同的算法去优化计算机的时间效率和空间效率。那么有什么数据机构还有算法有这么好的性能呢？先对这些数据结构分个类。

一、数据结构的分类

从上图可以看到，整个数据结构与算法研究的知识体系也就这么多。还记得刚刚提到的时间效率与空间效率嘛？逻辑结构与存储结构都是为其服务的。而数据的运算是时间效率和空间效率的表现形式。

二、数据结构的分析

数据之间的相互关系称之为逻辑结构。比如集合、线性结构（一对一）、树形结构（一对多）、图形结构（多对多）。

数据在计算机中的存储形式称之为存储结构。

1. 顺序存储：他是用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系
2. 链式存储：在每一个数据元素中增加一个存放地址的指针，用指针表示元素之间的逻辑关系。

三、时间复杂度与空间复杂度

在文章一开始就描述了时间效率和空间效率，那么他们两个该怎么使用数据去量化呢？或者说是我们该怎么去衡量时间效率和空间效率呢？这就用到了时间复杂度和空间复杂度。

1、首先看时间复杂度：

想要了解时间复杂度，就需要先了解时间频度。一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

接下来就引入了时间复杂度的概念。看一下比较官方的定义吧：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。是不是比较难以理解，说白了时间复杂度就是描述时间的规模，比如说时间频度是T(n),时间复杂度就是O(n)。时间频度是T(n+n)的时候,时间复杂度还是O(n)。也就是他的时间规模就是n这个层次了。

常见的算法的时间 复杂度之间的关系为：

O(1)<O(logn)<O(n)<O(nlog n)<O(n2)<O(2n)<O(n!)<O(nn)

举个例子吧：

 a=0； //（1）
 for(i=1;i<=n;i++) //（2）
 for(j=1;j<=n;j++) //（3）
 a++； //（4）

语句（1）执行1次，

语句（2）执行n次

语句（3）执行n2次

语句（4）执行n2次

T(n) = 1+n+2n2= O(n2)

2、空间复杂度

空间复杂度就比较容易理解了，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个空间规模，我们用 S(n) 来定义。

空间复杂度比较常用的有：O(1)、O(n)、O(n2)，