时间复杂度分析
最好、最坏、平均时间复杂度
数组
内存中一块连续的存储空间,有效使用 CPU 的缓存机制,可以很方便的定位元素
Hash 表
底层可以使用数组存储数据,借助 hash 函数找数据对应的下标
Hash 函数的其他用途
链表
栈 or 队列
栈是一种操作受限的数据结构,只支持入栈和出栈操作。后进先出是它最大的特点。(特定的数据结构是对特定场景的抽象)
树型结构
M 阶 B 树:结点最多有 M 个儿子。(概括来说是一个节点可以拥有多于2个子节点的二叉查找树)
要求:
B+树:(为了支持按照区间查找 和 减少去磁盘取数据)
树的遍历方式:根据根节点的遍历时间分为前中后序遍历
堆型结构
解决问题
排序
三个基本属性:时间复杂度、空间复杂度、排序算法的稳定性
排序算法的稳定性(排序后相等元素之间原有的先后顺序不变):稳定的排序算法,排序效果可以叠加。(例如按照时间+金额排序)(可以先按照时间排序、再按照金额执行排序)
冒泡排序:只循环比较相邻的数据,最大的数因为比较会下沉,较小的数会逐渐向上冒
插入排序:取未排序区间的元素,在已排序区间找合适的插入位置进行插入
选择排序:和插入排序的思想类似,不同点在于在没有排序的数组元素中进行交换找到最大或最小元素进行排序
查找
二分查找
字符串匹配算法
KMP 算法(K(m+n))参考链接
暴力匹配算法(k(nm))
四种常见算法
分治算法:将大的问题拆分成小问题,从子问题中得到原问题的解
回溯算法:遍历所有可选择元素或者数据,如果当前选择不符合问题要求就会产生回溯,即抛弃当前的选择回到上一个状态并进行其他的选择(类似于穷举的解决方式)
穷举算法:枚举法、暴力法,通过搜索所有的解空间得到问题的解
贪心算法:分阶段的工作,在每个阶段做出当前最好的选择,从而希望得到结果是最好或最优的算法
动态规划算法:需要满足(最优子结构、无后效性、重复子问题)
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。