O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2^)<O(n^3^)<O(^nk^)<O(2^n^)

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在O(1)O(1)O(1)时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

直接插入排序、折半插入排序、希尔排序

冒泡排序、快速排序

简单选择排序、堆排序

二路归并排序、多路归并排序

多关键字排序

快速排序、归并排序、希尔排序、堆排序O(nlog2n),其他的O(n^2^);

快速排序O(log2n)归并排序O(n)，基数排序O(rd)，其他的都是O(1);

快速排序、简单选择排序、堆排序、希尔排序 不稳定，其他的都是稳定的

动态规划算法的基本**是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

动态规划和回溯法最大的区别是：动态规划对组合不感兴趣，只关心组合的数目；回溯法需要列出所有的组合；

一个数组cost的所有数字都是正数，它的第i个数字表示在一个楼梯的第i级台阶往上爬的成本，在支付了成本cost[i]之后我们可以从第i级台阶往上爬1级或者2级。假设台阶至少有两级，我们可以从第0级台阶出发，也可以从第1级台阶出发，请计算爬上该楼梯的最少成本。例如输入数组[1, 100, 1, 1, 100, 1]，则爬上该楼梯的最少成本是4，分别经过下标为0、2、3、5这四级台阶

解决一个问题如果存在多种步骤，每个步骤存在若干选择问题，适合解决集合的排列，组合的很多问题；

列如求一个数组的所有子集，[1, 2]: [], [1], [2], [1, 2]