概念

时间复杂度和空间复杂度是用来衡量不同算法之间的优劣
时间复杂度：计算的不是算法运行的时间，而是算法运行执行语句的次数
空间复杂度：指一个算法在运行过程中，临时占用存储空间大小的度量，简单的说就是，被创建次数最多的变量，它被创建了多少次，那么这个算法的空间复杂度就是多少

量级以及计算方法

常用的时间复杂度量级

• 常数阶O(1)
  无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)；

  int i = 1;
  int j = 2;
  ++i;
  j++;
  int m = i + j;
  

• 线性阶O(n)
  for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

  for(i=1; i<=n; ++i)
  {
     j = i;
     j++;
  }
  

• 对数阶O(log₂n) ：常见于算法中先把数据对半分，然后计算，比如二分法查找

从下面的代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log₂n
也就是说当循环 log₂n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(log₂n)

int i = 1;
while(i<n)
{
  i = i * 2;
}

• 线性对数阶O(nlog₂n)：常见于算法中先把数据对半分，然后循环计算，比如归并排序
  将时间复杂度为O(log₂n)的代码循环N遍的话，那么它的时间复杂度就是 n * O(log₂n)，也就是了O(nlog₂n)。

  for(m=1; m<n; m++)
  {
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
  }
  

• 平方阶O(n²)：常见于算法中多次循环计算，比如冒泡排序，快速排序（最差情况）
  平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了

  for(x=1; i<=n; x++)
  {
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
  }
  

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。

空间复杂度比较常用的有：

• O(1)：如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

   int temp=0;
  for(int i=0;i<n;i++){
  temp = i;
  }
  

• O(n)
  算法循环n次，每次temp都会创建，所以空间复杂度是n

  for(int i=0;i<n;++){
  int temp = i;
  }
  

以归并排序为例，在合并过程中，每次都要比较交换，要比较n次，每次都创建一个临时变量，所以归并排序的空间复杂度为O(n)

• O(n²)
  同上，如果是两个for循环，同时每次都创建变量

• O(log₂n)
  同时间复杂度，算法循环log₂n次，每次都创建变量
  以快速排序为例，快排最好的情况下只需循环log₂n次，每次交换创建一个临时变量，最差情况下要循环n次，所有快速排序的空间复杂度为 O(log₂n) ~ O(n)