衡量一个算法的好坏，通常用时间维度和空间维度去衡量

时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是「鱼和熊掌」，不可兼得的，那么我们就需要从中去取一个平衡点。

时间复杂度

通常用O来表示，字母O，大O。
大O表示出了算法的速度，即执行时间。这里的时间不是指多少毫秒。偏向于「代码运行的次数」，但是不能用时间复杂度明确表示代码运行次数。准确地说，是算法运行时间的增速

举个例子：

小明心里想一个数，这个数在1-1000范围内。小红猜测一个数，小明告诉小红大了，还是小了。 小明想的678 小红猜测4，小了 9小了 56小了 ……… 如果小明想的是999 小红猜的从1开始，1,2,3…….. 1000个数最多猜1000次，1w个数最多就是猜1w次，1亿个数就是1亿次

这种算法的时间复杂度**O(n)**

时间复杂度表示的是最差的情况。n个数一个一个猜最多猜n次，最少1次。

经典二分法例子：

上面的猜数例子，1000个数，想的678. 第一次猜500，1-1000的中间值，小了 第二次猜750，500-1000的中间值，大了 第三次猜625，500-750的中间值，小了 ……..

反正几次就折中折出来了。
这个的时间复杂度是多少了？**O(logn)**

对数时间，对数是啥

N=ax(a>0,a!=1) , a的x次方等于N，那么数x叫做以a为底N的对数，记作 x=logaN，其中a叫做底数，N叫做真数，x叫做“以a为底N的对数”

210，10个2相乘大于1000，所以上面二分法的例子时间粒度为10，最多执行10次，而第一个例子，时间粒度是1000，最多1000次
数据大一点，40亿。第一个例子的时间粒度40亿，最多执行40亿，而第二个，时间粒度32左右，做多执行32次。

一个要执行几十亿次，而另一个只要执行几十次，差了几亿倍。

数据量小的时候速度倍率差距不大，数据量越来越多，时间复杂度带来的差异越来越大，所以时间复杂度用来表示算法执行时间的增速

时间复杂度的表示规则

  1. 常数时间复杂度，不管是多少，都用**O(1)**
  2. 有系数的去掉系数，执行2n次，时间复杂度**O(n)**
  3. 多项式，取最高次幂项，去掉系数，执行3n^2+4n+100次，时间复杂度**O(n^2)**

    常见的时间复杂度

    常数时间O(1)

    代码执行次数就是一个数，比如不管数据多少，就执行2次，8次或者1万次。执行一个固定的次数，如
    1. int i = 1;
    2. int j = 2;
    3. ++i;
    4. j++;
    5. int m = i + j;

    线性时间O(n)

    根据函数图像，执行的时间是一条直线，如
    1. for(int i=1; i<=n; i++)
    2. {
    3.  a[i]=i;
    4. }

    对数时间O(logn)

    1. int i = 1;
    2. while(i<n)
    3. {
    4.  i = i * 2;
    5. }
    6. //i的值2,4,8,16,32......
    从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方大于等于 n，那么 x = log2n
    也就是说当循环 log2n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)

    线性对数时间O(nlogn)

    线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。上面的代码改进一下
    1. for(int m=1; m<n; m++)
    2. {
    3.  i = 1;
    4.  while(i<n)
    5.  {
    6.      i = i * 2;
    7.  }
    8. }

    平方时间O(n²)

    平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。
    1. for(int x=1; x<=n; x++)
    2. {
    3. for(int i=1; i<=n; i++)
    4.  {
    5.    a[i]=x
    6.  }
    7. }
    这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n²)
    如果将其中一层循环的n改成m，那时间复杂度就是O(mn)，即：
    1. for(int x=1; x<=m; x++)
    2. {
    3. for(int i=1; i<=n; i++)
    4.  {
    5.    a[i]=x
    6.  }
    7. }
    其他的什么三次方，四次方，k次方复杂度同理上面的。
    算时间复杂度就大概估计一下代码执行的次数，写个函数表达式，这里要执行n次，这里执行3n次，那里执行n^2次，最后那里执行logn次。把这些像加起来，化简，再用时间复杂度的表示规则去掉系数，多余的项等，就算出的时间复杂度

    时间复杂度比较

    O(1) < O(logn) < O(n) < O(nlogn) < O(n**2) < O(n3) < O(2n**)

空间复杂度

和时间复杂度一样，同理。也是用大O表示，也不是用来表示准确的程序占用空间。表示一个大概。

如果程序所用的内存大小和数据量n没关系，空间复杂度就是O(1)，如

  1. int i =1;
  2. i++;
  3. i=i-3;

如果程序所用的内存空间和数据量n有关系，空间复杂度就是O(n)

  1. int[] a = new int[n]

参考

一套图 搞懂“时间复杂度” 算法的时间与空间复杂度（一看就懂）