前言
写了长一段时间代码，一直对数据结构与算法有些模糊的概念，一直都是调试调试，真成了代码的复杂粘贴的搬运工了，这里回顾数据结构与算法，算是修炼内功了吧，期望对自己的编程能力有所提高！
一、数据结构
1、什么是数据结构
数据结构是计算机存储、组织数据的方式。在现实世界中，不同数据元素之间不是独立的，而是存在特定关系的，我们将这些关系称为结构。同样在计算机中，数据元素也不是孤立、杂乱无序的，而是具有内在联系的数据集合。
数据元素之间存在的一种或多种特定关系，也就是数据的组织形式，叫数据结构。也可以说，数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。程序设计的实质就是数据结构和算法是设计，因此我们说
程序设计 = 数据结构 + 算法。
2、数据结构中结构的概念
数据结构中的结构，也就是我们研究的主体对象。数据结构中我们很少研究数据，因为数据在内存中的表现形式对于我们都是一样的，也就是二进制。传统上，我们把数据结构分为逻辑结构和物理结构。
逻辑结构
指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后关系，而与他们在计算机中的存储位置无关。逻辑结构分为以下四类：
集合结构
集合结构中的数据元素同属于一个集合，他们之间是并列的关系，除此之外没有其他关系。线性结构
线性结构中的元素存在一对一的相互关系。树形结构
树形结构中的元素存在一对多的相互关系。图形结构
图形结构中的元素存在多对多的相互关系。
物理结构
物理结构又叫存储结构，指数据的逻辑结构在计算机存储空间的存放形式。通俗的讲，物理结构研究的是数据在存储器中存放的形式。 存储器主要针对于内存而言，像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来描述。
数据在内存中的存储结构，也就是物理结构，分为两种：顺序存储结构和链式存储结构。
- 顺序存储结构
顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。数组就是顺序存储结构的典型代表。其在内存中的存储形式类似于下图：
- 链式存储结构
链式存储结构：是把数据元素存放在内存中的任意存储单元里，也就是可以把数据存放在内存的各个位置。这些数据在内存中的地址可以是连续的，也可以是不连续的。
和顺序存储结构不同的是，链式存储结构的数据元素之间是通过指针来连接的，我们可以通使用指针来找到某个数据元素的位置，然后对这个数据元素进行一些操作。如下图，可以帮助我们理解链式存储结构：
顺序存储结构和链式存储结构的区别
打个比方说一下顺序存储结构和链式存储结构的区别：
比如去银行取钱，顺序存储结构就相当于，所有的客户按照先来后到的顺序有序的的坐在大厅的椅子上（注意：是有顺序的坐着哦）。
而链式存储结构相当于，所有的客户只要一到银行，大堂经理就给他们每人一个号码，然后他们可以随便坐在哪个椅子上（随便坐，不需要按照什么顺序坐），只需要等待工作人员广播叫号即可。
而每个客户手里的号码就相当于指针，当前的指针指向下一个存储空间，这样，所有不连续的空间就可以被有顺序的按照线性连接在一起了。
二、算法
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
1、算法的基本特性：
- 输入输出，算法具有零个或多个输入，至少有一个或多个输出。
- 有穷性，算法在执行有限步后能够自动结束，不会出现无限循环。
- 确定性，算法的每一步都具有确定的含义，不会出现二义性。
- 可行性，算法的每一步都能够通过执行有限次操作完成。
2、算法的复杂度
算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。
时间复杂度
算法的时间复杂度反映了算法执行的时间长短，它是度量一个算法好坏的重要指标。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
度量一个算法的时间复杂度通常有两种方式：
- 事后统计法
- 事前分析法(大O表示法)
算法的时间复杂度是由最深层嵌套语句的频度决定的。
大O表示法的推导：
- 用常数1取代运行时间中的所有加法常数
- 在修改后的运行次数函数中，只保留最高阶
- 将最高阶系数变为1
例1:
int i, j, temp;
for(i=0; i<n; i++) {
for(j=i, j<n; j++) {
temp++;
}
}
语句执行的总次数：
所以其时间复杂度为O(n^2)。
例2:
for(i=1;i<=n;i=i*2){
System.out.println(i);
}
执行的总次数满足：
所以它的时间复杂度为O(logn)
例3：分析冒泡排序算法的时间复杂度
//冒泡排序算法
public static void bubbleSort(int[] data) {
if (data == null) {
return;
}
int temp = 0;
for (int i = data.length - 1; i > 0; --i){
for (int j = 0; j < i; ++j){
if (data[j + 1] < data[j]){
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
}
算法分析：
- 最佳情况下（初始状态是正序时），冒泡排序算法只需要一次扫描即可完成排序，此时比较次数 C_min = n - 1，移动次数 M_min = 0，所以时间复杂度为 O(n)
- 最差情况下（初始状态为逆序时），需要进行 n-1 次排序，每次排序进行 n-1 比较，此时比较次数 C_max = n(n+1)/2，移动次数 M_max = 3n(n+1)/2，所以时间复杂度为 O(n^2)
常见时间复杂度大小关系：
常见时间复杂度大小关系：
算法的时间复杂度和两个因素有关：算法中的最大嵌套循环层数；最大嵌套循环结构中每次循环的次数。一般来说，具有多项式时间复杂度的算法是可以接受的；具有指数时间复杂度的算法，只有当n足够小时才可以使用。一般效率较好的算法要控制在 O(N)或者O(log2 N)
空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。其中，n为问题规模，f(n)为语句关于n所占存储空间的函数。
算法的空间复杂度分析方法和算法的时间复杂度分析方法基本相同。
例如:
int i, j, temp;
for(i=0; i<n; i++) {
for(j=i, j<n; j++) {
temp++;
}
}
上方代码中，仅需为变量 i、j、temp分配空间即可，所以空间复杂度 S(n) = O(1)。
数据结构与算法总体图
参考
《大话数据结构》
//www.greatytc.com/p/9f23c9604a2e
