数据结构与算法简介

一、什么是数据结构
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
简括：存数据的，且存于内存中。

常见的数据结构
线性表：数组、链表、栈、队列
散列表：hash、位图
树：二叉树、多路树、堆
图：有向图、无向图、带权图

二、什么是算法
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
简括：算法是一种解决特定问题的思路
比如：LRU算法，解决的就是当空间不够用时，应该淘汰谁的问题，这是一种策略，不是唯一的答案，所以算法无对错，只有好和不好。

常见的算法
排序：冒泡、快速、插入、归并、计数排序、选择排序、堆排序、橘排序
其他：LRU、LFU、hash算法、一致性hash
算法思维：递归、回溯、分治、贪心、动态规划

三、算法复杂度
数据结构和算法本质上是“快”和“省”，所以代码的执行效率是非常重要的度量，我们采用时间复杂度和空间复杂度来计算。

时间复杂度
大O复杂度表示法

int sum(int n){
	int s=0; //t
	int i=1;  //t
	for(;i<=n;i++){ //t*n
		s=s+i; 		  //t*n
		}
		return s;	  //t
}
1
2
3
4
5
6
7
8

假设n=100，那么这段代码的执行次数等于
1 + 1 + 100n + 100n + 1 = 200n + 3
假设执行一行代码的时间为t，通过估算，代码的执行时间T(n)与执行次数成正比，记作
T(n) = O(f(n))
T(n)：代码执行时间
f(n)：每行代码执行次数总和
O：代码的执行时间与f(n)表达式成正比
上面的例子中T(n)=O(2n+2)，当n无限大时，低阶、常量、系统都可以忽略，所以T(n)=O(n)，即上列中的时间复杂度为0(n)，也就是代码执行时间随着数据规模的增加而增长。

int sum(int n){
	int s=0;
	int i=1;
	int j=1;
	for(;i<=n;i++){ //n
		j=1;
		for(;j<=n;j++){ //n*n
			s=s+i+j;	  //n*n
		}
	}
		return s;
}
1
2
3
4
5
6
7
8
9
10
11
12

上列中T(n)=O(n*n)，也就是代码执行时间随着数据规模的增加而平方增长
即上例中的时间复杂度为O(n^2)
时间复杂度也称为渐进时间复杂度。

计算时间复杂度技巧
（1）计算循环执行次数最多的代码
（2）总复杂度=量级最大的复杂度
（3）嵌套代码的复杂度等于嵌套内外代码复杂度的乘积（乘法法则）

常见的时间复杂度
O(1)
这是最简单的，也是最好理解的，就是常量级

O(logn)、O(nlogn)

i = 1;
while(i <= n){
	i = i * 2; //执行最多
}
1
2
3
4

2^x = n
x = log2n，忽略系数为logn，T(n)=O(logn)
如果将代码执行n遍，则时间复杂度记录为：T(n)=O(n*logn)，即O(nlogn)
比如：快速排序、归并排序的时间复杂度都是(nlogn)

O(n)
很多线性表的操作都是O(n)，这也是最常见的一个时间复杂度
比如：数组的插入删除、链表的遍历等

O(m+n)
m和n是代码的两个数据规模，而且不能确定谁更大，此时代码的复杂度为两段时间复杂度之和，即
T(n)=O(m+n)，记作：O(m+n)

O(m*n)
比如：嵌套for循环

空间复杂度
空间复杂度全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
由于现在硬件相对比较便宜，所以开发中常常会利用空间来换时间，比如缓存技术。
典型的数据结构中空间换时间是：跳跃表

为什么要学习数据结构和算法
（1）互联网行业中数据结构和算法尤为重要
互联网软件特点：高并发、高性能、高扩展、高可用、海量数据
（2）通关大厂面试必备技能
（3）能够更好的使用类库
（4）对编程的追求，精益求精