数据结构与算法简介

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

常见的数据结构
线性表:数组、链表、栈、队列
散列表: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
}

假设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;
}

上列中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; //执行最多
}

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)对编程的追求,精益求精


版权声明:本文为weixin_43526092原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。