我的数据结构与算法🥶
2021-06-28 22:59:39 278 举报
AI智能生成
数据结构与算法是计算机科学的两个核心领域,它们构成了解决复杂问题的基础。数据结构是一种特殊的方式,用于组织和存储数据,以便能够高效地访问和修改。常见的数据结构包括数组、链表、栈、队列、哈希表、树、图等。算法则是一系列定义良好的步骤,用于解决特定问题或执行特定任务。算法的效率通常通过时间复杂度和空间复杂度来衡量。常见的算法包括排序(如冒泡排序、快速排序)、搜索(如二分搜索、深度优先搜索、广度优先搜索)、动态规划、贪心算法等。理解和掌握数据结构和算法对于编写高效的软件程序至关重要。
作者其他创作
大纲/内容
工具
VSCode+LeetCode插件
LeetCode
复杂度
时间复杂度
概念
算法的时间复杂度,它反映的不是算法的逻辑代码到底被执行了多少次,
而是随着输入规模的增大,算法对应的执行总次数的一个变化趋势
而是随着输入规模的增大,算法对应的执行总次数的一个变化趋势
分类
常数复杂度
O(1)
含义
可能运算了1次,2次,3次,N次...
例子
Hash表
缓存
对数复杂度
O(logn)
线性时间复杂度
O(n)
含义
可能运算了n次,也可能运算2n次
例子
一层循环
线性对数时间
O(nlogn)
例子
二分查找
二叉搜索树
平方复杂度
O(n^2)
例子
两层循环
立方时间复杂度
O(n^3)
指数时间
O(2^n)
例子
递归
斐波拉契数列求第N项
阶乘
O(n!)
如何分辨时间复杂度
最常用的方式是直接看这个函数,或代码。它根据n的不同情况会运行多少次
空间复杂度
概念
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
和时间复杂度相似,它是内存增长的趋势
和时间复杂度相似,它是内存增长的趋势
分类
O(1)
对内存的占用量是恒定的
O(n)
最终的大小是由输入的 n 的大小决定的,它会随着 n 的增大而增大、呈一个线性关系
O(n^2)
例子
假如需要初始化的是一个规模为 n*n 的数组,那么它的空间复杂度就是 O(n^2)
O(1)<O(log2(n))<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
算法
排序
O(n^2)
冒泡排序
插入排序
选择排序
O(nlogn)
快速排序
归并排序
O(n)
桶排序
计数排序
基数排序
递归/分治
盗梦空间
终止状态
本层处理
Drill Down
本层状态清理
二分查找
有序
有界
能够通过索引随机访问
贪心算法
判断能不能贪心
弱化版的动态规划
动态规划
简单版本是递归加缓存
高级版本是递推公式
状态的定义
有些场景需要套用模板
最优子结构
状态转移方程
位运算
常见的位运算符有哪些
布隆过滤器
判断不存在100%准确
判断存在误差
利用Hash函数将待判断Key对应到多个位上
LRU
HashTable+双向链表
get set都是O(1)的复杂度
数据结构
非受限线性表
顺序结构
数组
特点
连续空间
查找速度快,插入删除节点慢
支持O(1)的随机访问
平均为O(n)的插入和删除
场景
创建数组
循环数组
添加元素
删除元素
插入元素
查找元素
链式结构
链表
特点
离散空间
查找慢,插入/删除节点快
场景
创建链表
添加元素
删除元素
插入元素
查找元素
分类
单链表
特点
不支持随机访问,需要顺序遍历去访问指定节点
插入和删除只需要移动指针,时间复杂度为O(n)
每个节点需要额外的空间存储指针,需要的内容比数组大
双链表
在单链表的基础上,除头节点外,每个节点多了一个存放当前节点内存地址的指针
循环链表
尾节点指针指向头节点
静态链表
借助数组,伴随指向后续节点的指针
数组与链表的区别
受限线性表
栈
特点
先进后出
比如:码砖,叠盘子
顺序和链式都可以实现
如何实现
push
pop
场景
浏览器的前进与后退
前后括号匹配
表达式计算
队列
特点
先进先出
比如:排队购物
顺序和链式都可以实现
如何实现
push
unshit
分类
普通队列
双边队列
入口和出口都可以进队和出队
优先级队列
根据优先级来出队
场景
LRU Cache
堆
大顶堆
小顶堆
场景
找第K大元素
树
二叉树
特点
顺序和链式都可以实现
三大组成部分
根节点
左子树
右子树
遍历方式
广度优先遍历
深度优先遍历
前序遍历
中序遍历
后序遍历
完全二叉树
满二叉树
二叉搜索树
平衡二叉搜索树
红黑树
AVL树
剪枝
哈弗曼树
字典树
特点:空间换时间
图
遍历时需要记录已经访问过的节点
映射
特点
K/V键值对,Key不重复
集合
Key不重复
并查集
站队问题
初始化
查询、合并
路径压缩
0 条评论
下一页