大O记法
1.时间复杂度
操作的速度，也称为时间复杂度，实际是指操作的步数。
2.二分查找与线性查找
线性查找就是按次序进行遍历
二分查找只适用于有序数组，就是每次从n/2处开始查找，
假如一个大小为N的有序数组，满足：
2^x = N，或2^x = N+1
那么最多需要x步完成查找。
3.大O记法
大O不关注算法所用的时间，只关注算法所用的步数。
举例，对于长度为N的普通数组进行线性查找：
根据下标查找数据：只需要拿到下标对于的内存地址，仅需1步，就能完成查找，因此记作O(1)
根据数据查找下标：需要遍历整个数组，对比要查找的数据位于哪个地方，该数据可能在数组末端，最多需花费N步进行对比，因此记作O(N)。注：大O一般记录都是指最坏情况(即数据在末端)。
O(1)就是用来表示所有数据增长但步数不变的算法。假如一个算法需要100步，数据无论怎么增加，还是需要100步，那么也可以计为O(1)
针对于二分查找呢
假设N个数，2\n\n^x =N，那么x=log(2)N，这里的2是底数，x是指数(即步数)，因此记作O(logN)
4.大O记法忽略常数
大O记法不包含一般数字，除非是指数，比如O(N/2)和O(2N)都记作O(N)，因为N/2和2N基本可以归纳为同类算法，大O记法只表明，对于不同分类，存在一临界点，在这一点之后，一类算法会快于另一类，并永远保持下去。至于这个点在哪里，大O 并不关心。
5.数组和链表
新建数组，会在内存中分配一块连续的内存地址，比如数组0000H~0009H，长度为10的数组。
新建链表(单向)，链表中每个节点的内存地址是随机分配的，每个节点会记录本节点的内存地址+下个节点的内存地址。
数组和链表都会记录第一个头部元素的内存地址。
因此：
根据下标查找的时候：
数组：内存的地址都是连续的，只需一次运算很容易找的该下标元素的内存地址，因此复杂度O(1)
链表：内存的地址都是非连续的，要找到第N个下标的元素，则先需要找到该元素的内存地址是多少，从首元素开始进行遍历，直到N元素，才能得知N元素的内存地址是多少，所以复杂度O(N)
查找元素：
数组：遍历所有元素，直到找到该元素，复杂度O(N)
链表：遍历所有元素，直到找到该元素，复杂度O(N)
删除元素：
数组：先查找到该元素，步骤为N，再删除，最坏情况为删除首元素，步骤为1(删除首元素)+(N-1)(修改1~N的内存地址)，复杂度O(2N),简化为O(N)
链表：找到该元素，步骤为N，再删除，修改前一个元素的“下节点”指向，步骤为1+1，复杂度O(N+2),简化为O(N)
插入元素：
数组：若为尾部添加，不需要修改0~N的内存地址，因此复杂度O(1)，若为首部添加，则需要以此移动0~N元素的内存地址，复杂度O(N+1),简化为O(N)
链表：若为尾部添加，则需要遍历整个链表，找到尾部元素的内存地址，然后将它指向新增的这个元素，复杂度O(N+1),简化为O(N),若为首部添加，则直接添加该元素并将它指向首部元素，成为新的首部，复杂度O(1)
6.二叉树
二叉树有点类似有序数组，左子节点-父节点-右子节点顺序排列，把这个小的“结构”看做一个顺序数组，因此：
查找：都相当于使用二分查找，复杂度O(logN)
插入：先查找到应当插入位置，再执行插入，步骤logN+1，忽略常数后，复杂度O(logN)
删除：稍微复杂，原理如下
a.如果要删除的结点没有子结点，那直接删掉它就好。
b.如果要删除的结点有一个子结点，那删掉它之后，还要将子结点填到被删除结点的位置上。
c.如果要删除的结点有两个子结点，则将该结点替换成其后继结点。一个结点的后继结点，就是所有比被删除结点大的子结点中，最小的那个。
如果后继结点带有右子结点，则在后继结点填补被删除结点以后，用此右子结点替代后继结点的父节点的左子结点。
简单来说就是，先查找到被删除的节点位置，步骤logN，被删除的节点如果有子节点，则将子节点按上述规则进行替补(其实就是修改子节点内存地址的过程),步骤为不确定的某个常数，因此删除的复杂度也为O(logN)
7.空间复杂度
空间复杂度也是用大O来表示，评估算法会消耗多少内存，这里的内存是根据额外需要(或者说额外"分配")的内存空间（也叫辅助空间）来算的，也就是说原本的数据不纳入计算。
参考《数据结构与算法图解》