所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法
大 O 复杂度表示代码执行时间或空间，随数据规模++的变化趋势，也叫作渐进时间复杂度 （asymptotic time complexity），简称时间复杂度。
数据规模：数据的 多少 或 大小时间 / 空间 时间：所有代码的执行时间 T(n) 与每行代码的执行次数 f(n) 成正比。即 T(n) = O(f(n))， 比如 T(n) = O(2n+2)空间：如 new int[] 特点：公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。只需要记录一个最大量级就可以了最多执行法则：在分析一个算法、一段代码的时间复杂度的时候，只关注循环执行次数最多的那一段代码就可以了
加法法则：总复杂度等于量级最大的那段代码的复杂度。将这个规律抽象成公式就是：
如果，T1(n)=O(f(n))，T2(n)=O(g(n))； 那么，T(n) =T1(n) + T2(n) = max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。将这个规律抽象成公式就是：
如果，T1(n) = O(n)，T2(n) = O(n) 那么，T1(n) * T2(n) = O(n^2)落实到具体的代码上，可以把乘法法则看成是嵌套循环
取反法则：O(f(n)) 也可以理解成，数据规模为 n 时代码需要执行的次数 f(n)。由于执行次数为 n 所能达到的数据规模好分析，所以我们可以先求出执行次数++与数据规模的变化规律，然后再取反
O(f(数据规模为n))= O(f ^ (-1)(执行次数为n))时间复杂度大致可以分为以下几个量级：
执行次数函数阶非正式术语12O(1)常数阶5log2^n + 20O(logn)对数阶2n + 3O(n)线性阶2n + 3nlog2^2 + 19O(nlogn)线性对数阶3n^2 + 2n + 1O(n^2)平方阶6n^3 + 2n^2 + 3n + 4O(n^3)立方阶2^nO(2^n)指数阶n* (n-1) * (n-2) … 2 * 1O(n!)阶乘阶对于上面罗列的复杂度量级，我们可以粗略地分为两类，多项式量级和非多项式量级。其中， 非多项式量级只有两个：O(2^n) 和 O(n!)。当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长，如下图： O(1)
O(1)即代码执行次数不受数据规模变化影响。
int i = 8; int j = 6; int sum = i + j;一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
O(logn)、O(nlogn)
i=1; while (i <= n) { i = i * 2; }从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。实际上，变量 i 的取值就是一个等比数列。如果把它一个一个列出来，就应该是这个样子的：2¹ 2² 2³ … 2x = n
所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2 =n 求解 x 这个 问题我们想高中应该就学过了，我就不多说了。x=log n，所以，这段代码的时间复杂度就 是 O(log n)。
另外，这里还可以用上面说到底取反法则进行分析。当代码执行 n 次时，能达到的数据规模是 2^n，所以取反得时间复杂度O(logn)。
注：O(nlogn)：可以通过乘法法则得到 O(n) * O(logn)，即外层再嵌套一层循环
for(j=1;i<arr.length;i++) { i = arr[i] while (i <= n) { i = i * 2; } }O(m+n)、O(m*n)
int cal(int m, int n) { int sum_1 = 0; int i = 1; for (; i < m; ++i) { sum_1 = sum_1 + i; } int sum_2 = 0; int j = 1; for (; j < n; ++j) { sum_2 = sum_2 + j; } return sum_1 + sum_2; }从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级 大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以， 上面代码的时间复杂度就是 O(m+n)。
针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(n))。
涉及到 if 的复杂度有四种：最好、最坏、平均，均摊。下面把他们分成两组来对比介绍…
最好情况时间复杂度 & 最坏情况时间复杂度
最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度 // n 表示数组 array 的长度 int find(int[] array, int n, int x) { int i = 0; int pos = -1; for (; i < n; ++i) { // 最好是arr[0]就匹配到，复杂度是O(1) // 最坏是arr[n-1]才匹配到，复杂度是O(n) if (array[i] == x) { pos = i; break; } } return pos; }平均情况时间复杂度 & 均摊时间复杂度
平均时间复杂度：适用于 for { if }，一般等于最坏情况复杂度均摊时间复杂度：适用于 if { for }，一般等于最好情况复杂度 // array 表示一个长度为 n 的数组 int[] array = new int[n]; int count = 0; // 向数组中添加元素 void insert(int val) { // 如果数组满了 // 此时就可以用到均摊复杂度。可以想到大部分情况下数组是没满的，所以均摊时间复杂度=最好时间复杂度=O(1) if (count == array.length) { int sum = 0; // 1.用sum来保存所有元素的和 for (int i = 0; i < array.length; ++i) { sum = sum + array[i]; } array[0] = sum; // 2.在arr[O]保存sum count = 1; // 3.清空数组 } // 将val插入 array[count] = val; ++count; }大部分情况下，我们并不需要区分最好、最坏、平均三种复杂度。平均复杂度只在某些特殊情况下才会用到，而均摊时间复杂度应用的场景比它更加特殊、更加有限。
空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模++的增长关系。而我们常见的空间复杂度就是 O(1)、O(n)、O(n )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。
空间复杂度 O(n) 代码示例：
void print(int n) { int i = 0; int[] a = new int[n]; for (i; i <n; ++i) { a[i] = i * i; } }第2 行代码中，我们申请了一个空间存储变量 i， 但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略
第 3 行申请了一个大小 为 n 的 int 类型数组
除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)
