时间复杂度

1.概念

时间复杂度表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

2.表示方法

T(n) = O(f(n))

n表示输入数据的规模大小，T(n)表示代码执行的时间，f(n)表示代码执行总次数的总和，O()表示T(n)与f(n)成正比。

3.时间复杂度分析

 int cal(int n) {
     int sum = 0;
     int i = 1;
     for (; i <= n; ++i) {
       sum = sum + i;
     }
     return sum;
 }

假设每一行普通的代码执行时间为time, 以上代码第二行和第三行执行时间分别为time1和time1，第三行和第五行的执行时间为timen和timen，所以执行总时间为(2+2n)*time，当n的值无限大的时候公式中低阶、常量和系数都可以忽略掉，所以上面代码的时间复杂度就可以表示为T(n) = O(n).

 int cal(int n) {
     int sum = 0;
     int i = 1;
     for (; i <= n; ++i) {
       sum = sum + i;
     }
     return sum;
 }

更具我们之前推导的方法，可以计算出执行总时间为(2+2n+3)*time，所以时间复杂度就表示为：T(n) = O()

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;
}

同分析得到以上代码的时间复杂度为O(m+n)。

4.常见时间复杂度

常量阶O(1)，线性阶O(n)，对数阶O(logn)，线性对数阶O(nlogn)，指数阶O()，阶乘阶O(n!)，平方阶O(),k次方阶O()
可以分为：多项式量级和非多项式量级，其中非多项式量级只有指数阶O()和阶乘阶O(n!)

对数阶举例：

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

可以看出i的变化是一个等比数列，假设循环执行了x次，那么i==n，求解得到x=logn，所以时间复杂度表示为O()

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

类似的我们求出时间复杂度为 O()，但是 就等于 * ，去掉常量系数，实际上也就表示为，所以对数阶统一表示为 O(logn)

空间复杂度

1.概念

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

2.表示方法

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

以上代码除了第三行的使用空间为n 的 int 类型数组，其它所占空间都为常量，所以整段代码的空间复杂度就是 O(n)。
我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，O(logn)、O(nlogn) 这样的对数阶复杂度平时都用用不到。