算法复杂度(几种常见算法求法总结)
1.什么是时间复杂度
概念:算法的时间复杂度是一个函数,算法中的基本操作的执行次数，为算法的时间复杂度。实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)
特殊情况:对递归来说,时间复杂度是单次递归乘上总的递归次数
2.什么是空间复杂度
在这个算法当中,函数创建的变量(对象)的个数关于问题规模N的数学表达式.
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因
此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
特殊情况:单次递归乘上递归深度(递归深度不是递归次数)
一般常见的空间复杂度有:O(N) O(1) O(N^2)
3.复杂度的考察方式
1.二分查找
因为二分查找每次排除掉一半的不适合值，所以对于n个元素的情况：
一次二分剩下：n/2
两次二分剩下：n/2/2 = n/4
…
m次二分剩下：n/(2^m)
在最坏情况下是在排除到只剩下最后一个值之后得到结果，即
n/(2^m)=1
所以由上式可得 ： 2^m=n
进而可求出时间复杂度为： log2(n)
2.各种排序的时间空间复杂度
3.实现一个算法,有时间空间复杂度的要求
4.按照特定时间空间复杂度对算法进行优化
线性表之顺序表
1.什么是顺序表?
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改.
2.顺序表分类
顺序表一般可以分为：
- 静态顺序表：使用定长数组存储元素。
- 动态顺序表：使用动态开辟的数组存储。
直接的区别在于:动态顺序表的底层空间是从堆上申请的.
3.顺序表基本操作(各种接口的实现)(待完善)
这部分内容专门写了博客,这里不写了.
4.顺序表的缺点
- 中间/头部的插入删除，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们
再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
5.顺序表的oj题
顺序表之链表
1.什么是链表
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
2.链表分类
一共八种分类:是否带头 单双向 是否循环
主要掌握:
1.不带头的单链表(面试常考)
2.带头双向循环链表(实际常用,c++标准库就提供这类链表)
3.链表常见oj题
单链表的逆置(非常非常常考)
求链表的中间节点(要求只能遍历一次)
求倒数第k个节点
栈(吃进去吐出来)
1.什么是栈
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。
2.栈的特性
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
3.栈的模拟实现(都有哪些接口(基本操作))
初始化 插入 删除 获取栈顶元素 获取有效元素个数 判空 销毁
4.栈的应用场景
1.可以用栈改变序列的次序(选择题)
2.检测括号匹配问题括号问题详解
3.对逆波兰表达式求值(c++)
4.将递归转化成循环(链表逆序打印,不让用递归让用循环,那就得用栈实现)
- 栈区 栈帧
看一看分享的博客"简析函数的调用过程",里面讲了详细的函数执行过程
还有以下这篇,写了栈区和栈帧
点击查看
队列(吃进去拉出来)
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
1.用顺序方式实现
入队列 :
可以 o(1)
出队列
方式一:直接头删 可以 …但是O(N)
方式二:让队头往后移动 可以…但是会假溢出
为了解决假溢出 ----->循环队列出现!
问题!!!
如何判断队列是空的还是满的
1.少用一个存储空间
2.使用标靶
3.使用计数
2.链式结构实现
很简单没有什么大问题.点击查看总结博客
3.栈和队列经典oj题(待完善)
括号匹配问题。括号问题详解
用队列实现栈。OJ链接
用栈实现队列。OJ链接
设计循环队列。OJ链接
二叉树
1.树的概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
注意：树形结构中，子树之间不能有交集，否则就不是树形结构
2.树的相关概念(叶子,双亲)
3.树的表示方法:
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间
的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法
等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
树的表示方法:孩子表示法 双亲表示法 孩子双亲表示法 孩子兄弟表示法
4.二叉树
4.1.二叉树概念
1.空树
2.非空:根节点+根的左子树+根的右子树(概念说明:1.递归 2. 有序)
注意:
- 二叉树不存在度大于2的结点
- 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
4.2.两颗特殊的二叉树:
1.满二叉树:每层节点都达到最大值
2.完全二叉树:假设高度为h ,前h层节点个数达到最大值,在第h层节点是从左往右的依次排列的
4.3二叉树的特性(这些性质要经常看!)
- 深度为h的二叉树的最大结点数是 2^h-1.
- 第k层节点个数:2^(k-1).
- 对任何一棵二叉树, 如果度为0的叶子结点个数为no , 度为2的分支结点个数为n2 ,则有 n0=n2+1.
- 针对完全二叉树:知道总节点个数:n 可以计算树的高度 :高度h=log(h+1),向上取整数.
- 节点个数为n,叶子数为**(n+1)/2**(n为奇数)或n/2(n为偶数).
- 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有：(可以找双亲 或者找孩子)
- 若i>0，i位置节点的双亲序号：(i-1)/2
- 左孩子序号为2i+1，若2i+1>=n则无左孩子
- 右孩子序号为2i+2，若2i+2>=n则无右孩子
4.4.二叉树存储(顺序式->堆,链式)
4.4.1.顺序方式存储(例如堆)
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树,比如堆,也只有堆是用数组来存储的.
原因就是说如果不是完全二叉树,那么有的位置是没有节点的,需要用标记空出位置,导致空间浪费.
4.4.2.堆
概念:
首先是一个完全二叉树,因为元素存储在数组中,并且对于任意节点满足比孩子大或者小
节点比孩子小,叫小堆,比孩子大,叫大堆.堆的性质：
堆顶元素一定是最大或者最小的.
堆里面每个节点都比孩子大或者小.
从根到叶子每条路径中的节点都是升序或者降序.堆的实现
创建(必须要用到向下调整,时间复杂度为O(logN))
向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
那么随机给你一个数组,并不满足根的左右子树都已经是堆的时候怎么办呢?
那么我们从最下面的一层入手,找到最后一个节点的双亲((i-1)/2),也就是倒数第一个非叶子节点,从这个节点开始应用向下调整.
插入(用向上调整,时间复杂度为O(logN))
删除(堆顶元素和最后一个元素交换删除,用向下调整时间复杂度为O(logN))
等等…不多写了…全在下面这博客里
堆的实现
- 堆的应用
堆排序
升序要大堆,降序要小堆
利用堆删除的思想排序
topk问题
在规模较大的数据中求最大或最小的前多少个元素
例如世界五百强
第一步是建堆,要的是前k个最大元素,创建小堆(与堆排序相反)小堆的根是最大的,大堆的根是最小的!
第二步找topk元素,用后续剩余的n-k个元素,依次与堆顶元素比较替换 第三步 最终堆中剩余的元素就是topk
这种问题一般应用在海量数据中,需要估算数据能否在内存中放得下.
假设有40亿个数据找前100个,就得看内存中能否存下40亿个数据 此处要了解一下对内存的估算.
- 建堆的时间复杂度计算
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的
就是近似值，多几个节点不影响最终结果)：
4.4.3.链式存储(一般二叉树)
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址 .链式结构又分为二叉链和三叉链,当前二叉树所用到的是二叉链,红黑树会用到三叉链.
4.4.4.二叉树的遍历
所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次.
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
- 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
- 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
- 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
前序遍历就是说,按照根->左->右的顺序,采取递归的规则
中序遍历就是说,按照左->根->右的顺序,采取递归的规则(就是把根放在中间就叫中序遍历).
后序遍历就是把根放在最后:左->右->根.
试着练习一下:下面这棵树的前中后序遍历
前序:ABDEHCFG(根左右)
中序:DBEHAFCG(左根右)
后序:DHEBFGCA(左右根)
还有一种层序遍历:设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
具体实现详见单独的二叉树实现(链式)博客…二叉树大总结