時間，空間復雜度分析

 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,代碼執(zhí)行時間與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
所有代碼的執(zhí)行時間與每行代碼執(zhí)行次數n成正比

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

三個較實用的時間復雜度分析：

1.只關注循環(huán)次數最多的那段代碼：

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

上訴列1，可以說明：T(n) = O(n),就是執(zhí)行時間最長的那段代碼。
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乘法規(guī)則：嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積

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為底的時間復雜度)
通過計算公式化簡可知：統(tǒng)稱為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