算法是指用來操作數(shù)據(jù)、解決程序問題的一組方法晋修。
一個算法的好壞是由它運(yùn)行所需要的時間和消耗的空間評定的。
也就是時間維度和空間維度，量化出來就是執(zhí)行當(dāng)前算法所消耗的時間（時間復(fù)雜`）和執(zhí)行當(dāng)前算法所占用的內(nèi)存空間（空間復(fù)雜度）秸仙。

時間復(fù)雜度

示例代碼：

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

假設(shè)每一行代碼的執(zhí)行時間都是time，那么

1. 第二行執(zhí)行的時間就是time
2. 第三行執(zhí)行的時間就是n*time
3. 第四行執(zhí)行的時間就是n*time
4. 第五行執(zhí)行的時間就是time

合計執(zhí)行的總之間是2time+ 2n*time桩盲。因此這段代碼執(zhí)行的總時間和每行代碼執(zhí)行的次數(shù)成正比寂纪！
將算法執(zhí)行的時間復(fù)雜度記為T(n)，使用O表示正比例關(guān)系赌结，因此就有：
T(n) = O(2n+2)捞蛋， 通用公式為T(n) = O(f(n))
這個公式只是監(jiān)禁時間復(fù)雜度公式，只表明代碼的執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢柬姚，簡稱時間復(fù)雜度
當(dāng)n趨近于無窮大時拟杉，常量2和首相系數(shù)2以及低階項可以省略掉，比如一個無窮大+100000000量承，結(jié)果還是無窮大搬设。
因此本算法的時間復(fù)雜度為T(n)=O(n)
通過其他實例可發(fā)現(xiàn)，同理可得撕捍，常見的時間復(fù)雜度常量級有：

1. 常數(shù)階--O(1)
2. 對數(shù)階--O(㏒??)
3. 線性階--O(n)
4. 現(xiàn)行對數(shù)階---O(n㏒??)
5. 平方階---O(n2)
6. 立方階---O(n3)
7. K次方階---O(n^k)
8. 指數(shù)階---O(2?)
   從上至下拿穴，時間復(fù)雜度越來越大，執(zhí)行效率越來越低

1. 常數(shù)階

示例：

int printNum(int i){
    int j = 1;
    j ++;
    return i+j;
}

無論代碼執(zhí)行了多少行忧风，只要沒有循環(huán)等復(fù)雜結(jié)構(gòu)默色，那么這個代碼時間復(fù)雜度都是O(1)，假設(shè)每行代碼執(zhí)行的時間都是time狮腿，代碼的行數(shù)是有限的即常量級別（實際開發(fā)函數(shù)中代碼不會超過80行腿宰，參見阿里巴巴Java開發(fā)手冊-2020最新嵩山版.pdf扬跋，提取碼：yxbz）斥黑，設(shè)為常數(shù)k镐依，那么執(zhí)行所花費(fèi)的時間為k * time责语，k為常數(shù)，因此時間復(fù)雜度為常數(shù)階规肴，表示為O(1)

2. 線性階

實例：

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

見本文開頭

3. 對數(shù)階

實例：

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

本實例中i的值乘以2以后越來越漸進(jìn)n捶闸，終將i >= n的時候退出循環(huán)，假設(shè)在循環(huán)了k次之后i = n拖刃，也就是說2 ^ k == n删壮，n = 2 ^ k，即k = ㏒??兑牡，即本算法的時間復(fù)雜度是O(㏒??)
部分資料對數(shù)階的復(fù)雜度寫為O(㏒?)央碟，是有問題的，對數(shù)函數(shù)只有在地數(shù)是e的時候用㏑?表示

4.線性對數(shù)階

實例：

for(int i = 0; i < n; i++){
    i = 1;
    while(i < n){
        i = i * 2;
    }
}

同上

5.平方階

實例：

int sum = 0;
for(int x = 0; x < n; x++){
  for(int j = 0; j < n; j++){
    sum = sum +x + j;
  }
}

此時的時間復(fù)雜度是O(n2)

均攤時間復(fù)雜度

ArrayList底層維護(hù)了一個數(shù)組均函，因此他的插入時間復(fù)雜度是O(1)
假設(shè)現(xiàn)在自己實現(xiàn)了一個ArrayList數(shù)組亿虽，每次空間用盡之后，新建一個新的數(shù)組苞也，帶下是原來的兩倍洛勉，使用for將舊數(shù)組的數(shù)據(jù)拷貝到新數(shù)組，那么此操作的時間復(fù)雜度就是O(n)如迟，每次的拷貝操作都是在進(jìn)行了n次時間復(fù)雜度為O(1)的插入操作之后進(jìn)行的收毫。那么把O(n)的時間復(fù)雜度操作均分到n次O(1)的操作上面，均攤下來幾乎所有的插入時間復(fù)雜度都是O(1)

空間復(fù)雜度

空間復(fù)雜度的全稱是漸進(jìn)空間復(fù)雜度殷勘，表示算法消耗的存儲空間和數(shù)據(jù)規(guī)模的增長關(guān)系此再。
通常使用S(n)來表示。
空間復(fù)雜度比較常用的有O(1)玲销、O(n)输拇、O(n2)

空間復(fù)雜度O(1)

實例：

int i = 1;
int j = 2;
j++;
i++;
int m = i * j;

算法中的變量所分配的空間都不隨著處理數(shù)據(jù)量變化，因此他的空間復(fù)雜度S(n) = O(1)

空間復(fù)雜度O(n)

實例：

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

這段代碼中贤斜，第一行new了一個數(shù)組出來策吠，這個數(shù)據(jù)占用的大小為n，這段代碼的2-6行瘩绒，雖然有循環(huán)猴抹，但沒有再分配新的空間，因此草讶，這段代碼的空間復(fù)雜度主要看第一行即可洽糟，即 S(n) = O(n)

文章參考：

1. 算法的時間與空間復(fù)雜度（一看就懂）
2. 一次搞懂時間復(fù)雜度和空間復(fù)雜度
   感謝兩位大牛炉菲！