文章小結

寫在最前面，本文主要介紹了如何能快速判斷代碼段的時間復雜度（記憶模版），如果您尋找的并非此類文章則不必繼續閱讀后文。

1.算法時間復雜度是什么

2. 常見的時間復雜度

• O(1) ：常量級
• O(n)：線性
• O(logn)：對數
• O(nlogn)
• O(n^2)：平方
• O(k^n)：指數級
• O(n!)：階乘級別

3.如何判斷代碼的算法時間復雜度

首先我們假設執行一行代碼需要的時間為1， 判斷代碼時間復雜度就是是看算法執行次數和n的關系。

例如：下面代碼的時間復雜度為O(1)

String dogName = "小黃";
Systerm.out.print("this is a dog " + dogName);

例2: 下面代碼片段中，代碼執行次數為n，代碼時間復雜度為O(n)。

for (int i=0; i<n; i++) {
    Systerm.out.print("get num " + i);
}

4.如何快速判斷代碼時間復雜度。

想要快速判斷代碼片段時間復雜度有兩個方法，記憶和公式。這里我們僅討論記憶，記住代表性的模板就可以快速判斷時間復雜度

// 時間復雜度：O(1)
int a = 1;
int b = 2;
Systerm.out.print("sum is" + (a+b));

// 時間復雜度：O(n)
for (int i=0; i<n; i++) {
    Systerm.out.print("get num " + i);
}

// 時間復雜度：O(n^2)
for (int j=0; j<n; i++) {
     for (int i=0; i<n; i++) {
       Systerm.out.print("get num " + (i+ j));
   }
}
// 時間復雜度：O(logn)
for (int i=0; i<n; i=i*2) {
    Systerm.out.print("get num" + i);
}

// 時間復雜度：O(2^n)
int fib(int n) {
　　if (n<=2) return n; 
　　return fib(n-1) + fib(n-2);
}

O(1)、O(n)、O(n^2) 相對比較容易理解，這里不在贅述。

分析下O(logn)是怎么得到的。
2^0 = 1
2^1 = 2
2^2 = 4
.....
2^k = n;  所以需要執行k次。k=log2n，系數可以忽略所以時間復雜度為 O(logn)。

通過圖例解釋下O(k^n)指數級算法復雜度。以n=6為例，分析Fun(6)的計算邏輯，依據Fun(n) = Fun(n-1) + Fun(n-2)，做如下圖的拆解。

5.延展內容。如何刷題（LeetCode）

區分業余和職業的最大區別在于是否有專項聯系。比如乒乓球運動員，專項發球練習，接球練習等等等。刷法也是一樣，不能只做一遍，針對弱項要多練。

•  做題方法
  • 多看幾遍題，或者和面試官去恩人，確保自己的理解是正確的。
  • 想所有可能的解題方法，同時比較時間和空間復雜度。
  • 做題
  • test case
• 切題方法
  • 第一遍
    • 5分鐘。讀題+思考。
    • 直接看答案。注意多解法，對比。
    • 背誦+默寫好的答案。
  • 第二遍
    • 馬上默寫背誦的答案-->提交LeetCode (尋找反饋)
    • 多種解法對比體會。
  • 第三遍
    • 24小時后重新做一遍
    • 針對不同解法的不熟練的要專項練習
  • 第四遍
    • 一周后反復練習相同的題目
  • 第五遍
    • 面試前反復練習