數(shù)據(jù)結(jié)構(gòu)和算法本質(zhì)就是幫我們用最快的時間和最少的空間來執(zhí)行我們的代碼雪营。所以弓千，執(zhí)行效率是衡量一個算法的非常重要的指標。那如何來計算你的算法代碼的執(zhí)行效率呢卓缰？這就需要時間计呈、空間復(fù)雜度來分析了。
有人可能會說征唬，我把代碼執(zhí)行一遍捌显，然后通過統(tǒng)計、監(jiān)控就能知道執(zhí)行的時間和需要的內(nèi)存大小总寒。干嘛還需要時間扶歪、空間復(fù)雜度來分析呢？我都能得到具體需要的時間和內(nèi)存了摄闸，還需要多此一舉嗎善镰？
首先，這種評估算法效率的方法沒有問題年枕，我們還給這種方法起了一個名字炫欺，叫事后統(tǒng)計法。但是這種方法有很大的局限性熏兄。
1. 測試結(jié)果受測試環(huán)境影響
測試環(huán)境的硬件對測試結(jié)果有非常大的影響品洛。比如树姨，同樣的代碼在i7和i5的機器上執(zhí)行，結(jié)果肯定是不同的桥状。還有可能在一臺機器上A代碼比B代碼執(zhí)行速度要快帽揪，我們換另外一臺機器卻得到相反的結(jié)果。
2. 測試結(jié)果受數(shù)據(jù)規(guī)模的影響
比如排序算法辅斟，原始數(shù)據(jù)如果有序度不一樣转晰，執(zhí)行的時間就會有很大的差別。原始數(shù)據(jù)規(guī)模的大小不同士飒，也可能會讓原來速度快的算法變成速度慢的查邢。
所以我們就需要一個不需要具體的測試數(shù)據(jù)來測試，就可以大概估算出執(zhí)行效率的方法变汪，就是時間侠坎、空間復(fù)雜度分析方法。
大O復(fù)雜度表示方法
我們通過度代碼裙盾，來估算出它執(zhí)行所需要的時間实胸，下邊來看一段具體的代碼。
public int Function(int n)
{
int sum = 0;
for(int i = 1; i <= n; i++)
{
sum += i;
}
return sum;
}
這里我們假設(shè)每一行代碼執(zhí)行的時間都是相同的為 t番官，那么第 3 行執(zhí)行的時間為 t庐完，第 4 和 6 行執(zhí)行了 n 次，需要時間為 2nt徘熔，總的時間為 (1+2n)t门躯，可以看出來總的代碼的執(zhí)行時間 T(n) 與每行代碼的執(zhí)行次數(shù)成正比。
然后我們再來看下邊的代碼
public int Function(int n)
{
int sum = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++
{
sum += i*j;
}
}
return sum;
}
這段代碼中在上邊的基礎(chǔ)上又套了一層 for 循環(huán)酷师，第 6 和 8 行執(zhí)行了 次讶凉，需要的時間為
,總的需要的時間為
通過上述兩個具體的代碼例子我們總結(jié)出一個公式：
T(n) 表示代買執(zhí)行的時間，n 是數(shù)據(jù)的大小山孔，f(n) 表示代碼執(zhí)行的總次數(shù)懂讯，O 表示公式中 T(n) 與 f(n) 成正比。這就是大 O 時間復(fù)雜度表示法台颠，它實際上并不表示代碼具體執(zhí)行所需要的時間褐望，它表示隨著數(shù)據(jù)規(guī)模的變化代碼執(zhí)行時間的變化趨勢。
當 n 非常大時串前，低階瘫里、系數(shù)、常量對結(jié)果的影響就非常小了荡碾，所以我們可以把這幾項忽略不記谨读，只保留最高階的就可以了，所以上邊兩個例子中 就可以記為
坛吁，
就可以記為
劳殖。
上邊我們知道了怎么用大 O 時間復(fù)雜度的表示方法贼邓。那么我們?nèi)绾尉唧w分析一段代碼的時間復(fù)雜度呢？
- 只關(guān)注循環(huán)次數(shù)最多的一段代碼
因為大 O 時間復(fù)雜度只表示一種變化的趨勢闷尿，所以我們只需要關(guān)心階數(shù)最高的那部分就可以了，低階女坑、系數(shù)填具、常量我們都可以忽略。以上邊第一段代碼為例 匆骗，我們忽略掉系數(shù)和常量最后就得到了
劳景。
- 加法法則
對于順序執(zhí)行的長代碼，我們把它分成幾部分碉就，分別求出其總時間 T(n) ,然后相加得到總的時間盟广，最后同樣忽略低階、系數(shù)瓮钥、常量部分筋量，保留最高階的部分然后得出最后的時間復(fù)雜度大 O。
- 乘法法則
對于邏輯復(fù)雜的嵌套代碼碉熄，我們分別求嵌套內(nèi)外代碼的復(fù)雜度桨武，然后相乘得出最終的時間復(fù)雜度大 O。
幾種常見的時間復(fù)雜度分析
下邊列舉出常見的時間復(fù)雜度量級
| 多項式量級 | 非多項式量級 |
|---|---|
| 常數(shù)階 |
指數(shù)階 |
| 對數(shù)階 |
階乘階 |
| 線性階 |
|
| 線性對數(shù)階 |
|
| k次方階 |
對于非多項式量級的算法會隨著數(shù)據(jù)規(guī)模的增大急劇增加锈津，所以分多項式量級的算法是非常低效的呀酸，我們不做過多的介紹。主要來介紹幾種常見的多項式量級的時間復(fù)雜度琼梆。
- 常數(shù)階
只是常量級時間復(fù)雜度的表示方式性誉，不是只有一行代碼，而是每一段代碼的執(zhí)行時間不隨著 n 的數(shù)據(jù)規(guī)模的變大而變長茎杂，這樣的代碼的時間復(fù)雜度記為
错览。
- 對數(shù)階
對數(shù)階復(fù)雜度很常見，但是分析的時候卻不容易蛉顽，下面我們用一段實際的例子來看看對數(shù)階時間復(fù)雜度蝗砾。
public void Function(int n)
{
int i = 1;
while(i<=n)
{
i = i*2;
}
}
通過上邊我們總結(jié)的方法，我們只需要知道 while 循環(huán)的次數(shù)携冤，就能得到這段代碼的復(fù)雜度悼粮。從代碼中可以看出 i 的值從 1 開始，每循環(huán)一次乘以 2曾棕，直到 i 的值大于 n 的時候結(jié)束扣猫，我們得到規(guī)律然后把結(jié)果列出來，
翘地，然后求得執(zhí)行的次數(shù)
,這段代碼的時間復(fù)雜度就是
申尤。
我們再來講一種跟前面都不一樣的時間復(fù)雜度癌幕，代碼的復(fù)雜度由兩個數(shù)據(jù)的規(guī)模決定，所以我們需要同時考慮兩種數(shù)據(jù)規(guī)模對結(jié)果的影響昧穿，如果是順序的勺远，那么時間復(fù)雜度就為 ，如果為嵌套的那么時間復(fù)雜度為
时鸵。
空間復(fù)雜度分析
理解了上邊的時間復(fù)雜度的分析方法胶逢，空間復(fù)雜度的分析也就很簡單了∈吻保空間復(fù)雜度表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系初坠。
同樣我們通過一段實際的代碼來分析一下。
public void Function(int n)
{
int i = 0;
int[] a = new int[n];
for(i;i<n;i++)
{
a[i] = i*i;
}
}
我們看到第 3 行代碼彭雾，我們申請了一個空間存儲變量 i 碟刺，但是這個是常數(shù)階的，不會隨 n 的變化而變化薯酝，所以可以忽略半沽，第 4 行我們申請了一個大小為 n 的 int 類型數(shù)組，除此之外其余代碼沒有占用其他的空間蜜托，所以這段代碼的空間復(fù)雜度為 抄囚。
我們常見的空間復(fù)雜度有 、
橄务、
幔托，對數(shù)階的空間復(fù)雜度一般情況下用不到。所以空間復(fù)雜度比時間復(fù)雜度容易分析的多蜂挪，我們也只需要掌握常見的幾種就可以了重挑。
最后我們總結(jié)一下常見的幾種復(fù)雜度，執(zhí)行效率從高到低依次為
