时间与空间的复杂度分析：

时间，空间复杂度分析

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }
可以先分析对于每行代码，我们假设为unit_time=1,可以得出整个代码的运行时间为2n + 2
故T1(n) = 2n + 2,代码执行时间与n成正比

例子2：

 int cal(int n) {
   int sum = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1;
     for (; j <= n; ++j) {
       sum = sum +  i * j;
     }
   }
 }
由上述代码可知，同样对于每行代码的运行时间为单位unit_time,可得：T2(n) = 2n*n + 2n + 3
所有代码的执行时间与每行代码执行次数n成正比

通过上述两个列子的描述，可以得出用公式表示法：
T(n) = O(f(n))
由此可以得出：T1(n) = O(f(n)) = O(n),T2(n) = O(n*n)

三个较实用的时间复杂度分析：

1.只关注循环次数最多的那段代码：

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

上诉列1，可以说明：T(n) = O(n),就是执行时间最长的那段代码。
2.加法法则：总时间复杂度 = 量级最大的那段代码的复杂度
转换成时间代码公式为：
T(n) = T1(n) + T2(n) = max(O1(f(n)),O2(f(n)))

int cal(int n) {
   int sum_1 = 0;
   int p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }

   int sum_2 = 0;
   int q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
 
   int sum_3 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }
由此可知：T(n) = O(n*n)

3乘法规则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

int cal(int n) {
   int ret = 0; 
   int i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i);
   } 
 } 
 
 int f(int n) {
  int sum = 0;
  int i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
 }
由此可知：该代码的复杂度T(n) = T1(n) *T2(n) = O(n*n)

几种常见的时间复杂度分析：

1.O(1)

 int i = 8;
 int j = 6;
 int sum = i + j;
只要代码里复杂度不会随着n增大而增大，就是常量

2.O(log n)，O(n log n)

 i=1;
 while (i <= n)  {
   i = i * 2;
 }
时间复杂度：log 2 n(以2为底的对数)
i = 1;
while(i <=n){
  i = i * 3;
}
时间复杂度：log 3 n(以3为底的时间复杂度)
通过计算公式化简可知：统称为log n

3.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;
}
时间复杂度：O(m+n)
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]
  }
}
两者时间复杂度：T1(m) *T2(n) =O(f1()*f2()) 

空间复杂度分析：

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的O(1),
有n的话：O(n),O(n*n)

总结：

Screenshot.png