时间、空间复杂度



关注最大阶,忽略系数、低阶、常数 ; 2n2+2n +10000 => O(n2)



O(1) : 执行时间不随 n 的增大而增长, 没有循环、递归，即使有成千上万行，都是O(1)



O(logn):



O(nlogn): 把O(logn)的代码执行n遍



均摊时间复杂度：一个算法，操作最耗时的一种情况，是否可以平摊到其他的不耗时的操作上，如果可以，一般均摊时间复杂度为最好情况的复杂度。



数组



定义：使用连续的存储空间存放相同数据类型数据的线性表

特性：随机访问；下标访问时间复杂度O（1）；低效的中间、开头插入和删除

适用场景：正常开发，用动态数组替代， 如果是特别底层的开发，使用数组可能会更合适



链表

• 双向链表：

在已知链表节点情况下，插入、删除比单向链表更快，O(1)复杂度；如果是有序的链表，在查找元素时，可以每次记录上次查找的结果，通过与上次的值比较，可以知道向前还是向后查找，比单向链表快。

空间换时间思想



• 和数组的访问效率差异： 数组读取可以借助 CPU 的缓存机制，预读数组中的数据（cpu从内存读取数据，不只是读取要访问的那个地址，而是把一个连续的数据块读取到cpu缓存，以供下次使用）。由于数组连续存储，而链表的内存分布在各处，所以访问效率更高。



栈

• 特点：先进先出

• 应用：

• 函数调用栈

• 表达式求值，一个操作数栈，一个操作符栈



队列

• 特点：先进后

• 顺序队列：用数组实现。链式队列：用链表实现

• 循环队列判断是否已满条件：（tail + 1）% n == head

实现出循环队列--方式1：比较head和tail的值， 方式2：用size记录队列大小

• 应用场景：对大部分资源有限的场景，当没有空闲资源时，基本都可以通过“队列”这个方式来实现请求排队，削峰填谷。



递归

可用递归来解决的问题要满足3个条件：

1. 问题可以拆解成几个更小的子问题

2. 分解后的子问题，除了数据规模不一样，求解思路完全一样

3. 存在递归终止条件



写出递归代码方法：写出递推公式，找到终止条件。

递归是把问题传递出去，回来的过程为“归”。

把他抽象成一个公式，不用想每一层的调用关系，不用试图分解每一个步骤，只需假设分解出的子问题都解决了，分析主问题和其他子问题的关系



• 注意事项

使用递归时，警惕堆栈溢出，系统栈一般不大，容易造成堆栈溢出。

要小心重复计算问题：随着调用层次深入，可能会分解出相同的子问题，而这些子问题会重复计算。虽然可以用一个map来缓存已经计算过的问题，但函数调用带来的开销依然很高。递归每调用一次，都要保存一份现场数据到内存栈，空间复杂度为O（n）



跳表



• 特点：一个已排序的链表 + 多个用于作索引的链表；

可以动态高效插入、删除，O（logn）；

查找速度类似于二分查找；

有着树一样的搜索性能；

• 应用：redis上的有序集合使用跳表实现：

——按照区间查找数据比红黑树更快，O（logn）

——代码更容易实现，不易出错

——可以通过改变索引策略，来平衡执行效率和空间的开销，索引间隔为2最快



树



平衡二叉树

• 定义：任意一个节点，它的左右子树高度差不能超过1。

AVL树严格符合这个标准，它高度平衡，但是删除、插入相对耗时，不适用频繁变动的树

红黑树做到了近似的平衡，各种操作性能非常稳定，工业级的平衡二叉查找树

• 目的：解决树在频繁的插入、删除等修改后，可能导致查找时间复杂度退化的问题（慢慢的长得像个链表，两边不再平衡）



• 和其它功能类似的结构体对比：

散列：

——优势：操作耗时，O(1)

——劣势：无序动态扩容和缩容性能不稳定；额外需要O（n）空间；散列冲突；散列函数设计要求高

——应用场景：数据变化不大，内存不敏感

跳表：

——优势：数据有序

——劣势：额外需要O(n)空间，操作耗时O(n)

——应用场景：内存不明感，需要数据有序的地方（顺序遍历、区间查找）

红黑树：

——优势：性能非常稳定，不额外占用空间，比散列应用了更多地方。中序遍历就是顺序遍历

——劣势：难理解，操作O(n)，区间查找复杂度O(n)

——应用场景：内存敏感，对性能稳定性要高特别高



贪心算法

• 使用场景：在给定的限制值下获得一个最大的期望值，每次操作都要对期望值贡献最大。

• 缺点：并不是每次都可以得出最优解



动态规划



• 原理：把问题分解为多个阶段，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合（用于减少重复计算），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。

• 组成： 阶段 + 状态（取/不取/最值）

• 适用场景：求最优解

• 优点：相对于用回溯法，可以非常显著的降低时间复杂度