如何衡量算法的好壞

根據(jù)時(shí)間復(fù)雜度和空間復(fù)雜度來判斷?

比較項(xiàng)目	時(shí)間復(fù)雜度	空間復(fù)雜度
定義	衡量算法執(zhí)行時(shí)間與問題規(guī)模之間的關(guān)系	衡量算法在運(yùn)行過程中所占用的額外存儲(chǔ)空間與問題規(guī)模之間的關(guān)系
表達(dá)方式	通常用大O符號(hào)表示，如O（n）、O(n^2）等	通常用大O符號(hào)表示，如O（n）、O（1）等
關(guān)注重點(diǎn)	算法執(zhí)行時(shí)間的增長(zhǎng)速度	算法所需額外空間的增長(zhǎng)速度
影響因素	算法中基本操作的執(zhí)行次數(shù)	算法所需的額外數(shù)據(jù)結(jié)構(gòu)占用的空間大小
舉例	順序查找的時(shí)間復(fù)雜度為 O (n)，隨著數(shù)據(jù)規(guī)模 n 的增大，查找時(shí)間線性增長(zhǎng)	使用一個(gè)固定大小的變量，空間復(fù)雜度為 O (1)；使用一個(gè)長(zhǎng)度為 n 的數(shù)組，空間復(fù)雜度為 O (n)

大O的漸進(jìn)表示法

【實(shí)例1】

推導(dǎo)大O階方法

1. 用常數(shù)1取代運(yùn)行時(shí)間中所有的加法常數(shù)
2. 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)
3. 如果最高階項(xiàng)存在且不為1，則去除與這個(gè)項(xiàng) 相乘的常數(shù)，得到的結(jié)果就是大O階

使用大O的漸進(jìn)表示法后，Func1的時(shí)間復(fù)雜度為O（N^2）

我們平時(shí)所說的時(shí)間復(fù)雜度和空間復(fù)雜度都是在在最壞情況下的時(shí)間復(fù)雜度

拓展：怎么計(jì)算平均時(shí)間復(fù)雜度

算平均時(shí)間復(fù)雜度就是把每種情況出現(xiàn)的概率乘以在這種情況下算法花的時(shí)間，然后把所有這些結(jié)果加起來。

平均時(shí)間復(fù)雜度計(jì)算公式：

常見時(shí)間復(fù)雜度計(jì)算舉例

【實(shí)例1】知到循環(huán)次數(shù)的時(shí)間復(fù)雜度

【實(shí)例2】不知循環(huán)次數(shù)的時(shí)間復(fù)雜度

【實(shí)例3】常數(shù)次執(zhí)行的時(shí)間復(fù)雜度

【實(shí)例4】冒泡排序的時(shí)間復(fù)雜度

小tips：求復(fù)雜度一定要結(jié)合算法思想！并不一定兩個(gè) for循環(huán)嵌套，時(shí)間復(fù)雜度O(N)=N^2

【實(shí)例5】二分查找的時(shí)間復(fù)雜度

【實(shí)例6】階乘遞歸的時(shí)間復(fù)雜度

【實(shí)例7】斐波那契的時(shí)間復(fù)雜度

空間復(fù)雜度

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的度量，空間復(fù)雜度算的是變量的個(gè)數(shù)，使用大O漸進(jìn)表示法。

通俗來講，空間復(fù)雜度就是看這個(gè)算法在運(yùn)行過程中額外占用了多少內(nèi)存空間。

【實(shí)例1】冒泡排序的空間復(fù)雜度