時(shí)間抬探，空間復(fù)雜度分析

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }
可以先分析對(duì)于每行代碼苹享，我們假設(shè)為unit_time=1,可以得出整個(gè)代碼的運(yùn)行時(shí)間為2n + 2
故T1(n) = 2n + 2,代碼執(zhí)行時(shí)間與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;
     }
   }
 }
由上述代碼可知弧可，同樣對(duì)于每行代碼的運(yùn)行時(shí)間為單位unit_time,可得：T2(n) = 2n*n + 2n + 3
所有代碼的執(zhí)行時(shí)間與每行代碼執(zhí)行次數(shù)n成正比

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

三個(gè)較實(shí)用的時(shí)間復(fù)雜度分析：

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

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

上訴列1筷厘，可以說(shuō)明：T(n) = O(n),就是執(zhí)行時(shí)間最長(zhǎng)的那段代碼驼修。
2.加法法則：總時(shí)間復(fù)雜度 = 量級(jí)最大的那段代碼的復(fù)雜度
轉(zhuǎn)換成時(shí)間代碼公式為：
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ī)則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積

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;
 }
由此可知：該代碼的復(fù)雜度T(n) = T1(n) *T2(n) = O(n*n)

幾種常見(jiàn)的時(shí)間復(fù)雜度分析：

1.O(1)

 int i = 8;
 int j = 6;
 int sum = i + j;
只要代碼里復(fù)雜度不會(huì)隨著n增大而增大，就是常量

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

 i=1;
 while (i <= n)  {
   i = i * 2;
 }
時(shí)間復(fù)雜度：log 2 n(以2為底的對(duì)數(shù))
i = 1;
while(i <=n){
  i = i * 3;
}
時(shí)間復(fù)雜度：log 3 n(以3為底的時(shí)間復(fù)雜度)
通過(guò)計(jì)算公式化簡(jiǎn)可知：統(tǒng)稱(chē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;
}
時(shí)間復(fù)雜度：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]
  }
}
兩者時(shí)間復(fù)雜度：T1(m) *T2(n) =O(f1()*f2()) 

空間復(fù)雜度分析：

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]
  }
}
空間復(fù)雜度分析：沒(méi)有n的O(1),
有n的話：O(n),O(n*n)

總結(jié)：

Screenshot.png