這個(gè)系列已經(jīng)拖更好久了, 今天就來第二講吧, 這里聲明一下, 沒有特殊說明的情況下, 我們這個(gè)系列用的都是偽代碼, 這樣可以減少大家的學(xué)習(xí)成本, 任何語言都不影響學(xué)習(xí)算法

概念

• 時(shí)間復(fù)雜度: 執(zhí)行算法所需要的計(jì)算工作量
• 空間復(fù)雜度: 執(zhí)行算法所需要的內(nèi)存空間

一般情況下, 尤其是算法面試中, 我們更側(cè)重于考慮時(shí)間復(fù)雜度, 所以我們今天的重點(diǎn)是討論時(shí)間復(fù)雜度

從一個(gè)簡單的問題開始

從數(shù)組中查找一個(gè)數(shù)
這里我們考慮最差的情況, 我們要查的這個(gè)數(shù)在數(shù)組的最后一個(gè)位置上, 我們假設(shè)每查找數(shù)組中的一個(gè)數(shù)需要1ms

• 數(shù)組長度為10的時(shí)候, 我們需要10ms能得到這個(gè)數(shù)
• 數(shù)組長度為10000的時(shí)候, 我們需要10000ms能得到這個(gè)數(shù)
• 數(shù)組長度為1000000的時(shí)候, 我們需要100000ms能得到這個(gè)數(shù)

從上面的例子我們可以看出, 我們得到這個(gè)數(shù)所需要的事件取決于這個(gè)數(shù)組的長度, 或者取決于我們操作數(shù)組查詢的次數(shù), 我們假設(shè)數(shù)組的長度為n, 那么我們得到想要的數(shù)需要的時(shí)間就是n，拋開具體的單位和數(shù)組長度, 抽象出來的這個(gè)n就是我們的時(shí)間復(fù)雜度

什么是時(shí)間復(fù)雜度

• 在計(jì)算機(jī)科學(xué)中, 算法的時(shí)間復(fù)雜度是一個(gè)函數(shù), 他定量描述了該算法的運(yùn)行時(shí)間
• 以算法輸入值規(guī)模n為自變量的函數(shù)： T(n) = O(f(n))

上面這兩個(gè)定義我估計(jì)可能大家也看不懂, 當(dāng)然能看懂最好, 看不懂倒也沒太大影響, 一般情況下我們表示函數(shù)的邊界有下面三個(gè)符號(hào):

時(shí)間復(fù)雜度

• big O表示函數(shù)的上界
• big Ω表示函數(shù)的下界
• big θ表示函數(shù)的確界

通常我們描述的時(shí)間復(fù)雜度就是big O

big O(這個(gè)是字母O, 不是數(shù)字0) 的例子

假設(shè)我們有以下時(shí)間復(fù)雜度

1. 當(dāng)n=1, 4n²比2n項(xiàng)大2倍
2. 當(dāng)n=500時(shí), 4n²比2n大1000倍
3. 隨著n的增大, 4n²會(huì)遠(yuǎn)遠(yuǎn)大于2n, 2n對(duì)于表達(dá)式值得影響可以忽略不計(jì)

所以我們得到big O的方法就是去除低階項(xiàng), 保留高階項(xiàng)目, 并忽略系數(shù)

這個(gè)復(fù)雜度的高階項(xiàng)是4n², 所以2n+1就被去除了, 并且要忽略系數(shù), 所以4也就不需要了
最終這個(gè)時(shí)間復(fù)雜度就剩下了n², 因此我們有以下結(jié)論:

下面給出各種常用時(shí)間復(fù)雜度的比較

最好情況, 最壞情況, 期望情況

還是用上面數(shù)組中查找一個(gè)數(shù)的例子

• 最好情況: 目標(biāo)值是數(shù)組第一個(gè)元素, T(n)=O(1)
• 最壞情況： 目標(biāo)值是數(shù)組最后一個(gè)元素: T(n)=O(n)
• 期望情況(平均情況): T(n) = O(n)

一般情況下, 最好情況對(duì)于我們研究算法復(fù)雜度沒有實(shí)際意義, 一般我們只討論最壞情況和期望情況, 大部分情況下這兩中情況復(fù)雜度是一樣的, 但是也有部分特殊情況, 比如快排這兩種情況下的復(fù)雜度就不相同

一般問題的時(shí)間復(fù)雜度計(jì)算

我們一般分三個(gè)部分考慮:

• 基本操作的時(shí)間復(fù)雜度
  • 丟棄常數(shù)項(xiàng)
  • 丟棄次要項(xiàng)
• 基本操作被執(zhí)行了多少次(for/while循環(huán))
• 復(fù)合操作: 加還是乘

丟棄常數(shù)項(xiàng)的情況

下面有兩組代碼:

int min = Integer.MAX_VALUE;
int nax = Integer.MIN_VALUE;
for(int num : array) {
  if(num < min) min = num;
  if(num > min) max = num;
}

int min = Integer.MAX_VALUE;
int nax = Integer.MIN_VALUE;
for(int num : array) {
  if(num < min) min = num;
}

for(int num : array) {
  if(num > min) max = num;
}

第一組代碼, for循環(huán)的時(shí)間復(fù)雜度O(n), 進(jìn)行了一次所以時(shí)間復(fù)雜度是O(n)

第二組代碼, 進(jìn)行了量詞循環(huán)所以時(shí)間復(fù)雜度是O(2n)叔磷，我們說過算復(fù)雜度的時(shí)候要忽略系數(shù), 所以時(shí)間復(fù)雜度也是O(n)

丟棄次要項(xiàng)的情況

O(5 * 2ⁿ + 1000 * n²)
從上面時(shí)間復(fù)雜度比較的圖我們知道, 2^n 比 n^2 高階, 所以去掉n^2, 所以時(shí)間復(fù)雜度是O(2ⁿ)

復(fù)合操作: 加還是乘

假設(shè)我們算法有兩步, 每一個(gè)的時(shí)間復(fù)雜度分別為O(A)和O(B)

for(int a : arrA) {
  print(a)
}

for (int b: arrB) {
  print(b)
}

上面的代碼, 我們分別遍歷一次A數(shù)組和B數(shù)組, 遍歷A數(shù)組的時(shí)間復(fù)雜度為O(A), 遍歷B數(shù)組的時(shí)間復(fù)雜度為O(B)

這種情況下時(shí)間復(fù)雜度就是O(A+B)

for(int a: arrA) {
  for(int b: arrB) {
    print(b)
  }
  print(a)
}

上面的代碼, 我每進(jìn)入一次數(shù)組A循環(huán), 就要整個(gè)遍歷一遍B數(shù)組, 所以這種情況下時(shí)間復(fù)雜度是O(A*B)

我們來一個(gè)例子, 看大家到底有沒有理解一般情況的時(shí)間復(fù)雜度的計(jì)算

for(i=0; i<n; i++) {
  for(j=i+1; j<n; j++){
    print('a')
  }
}

我們來用最笨的辦法來分析:
這道題我們每進(jìn)入一次i循環(huán), j循環(huán)的總數(shù)就少一次, 什么意思呢假設(shè)n=5,
第一次進(jìn)入i循環(huán)
j = 1, 所以打印四次a

第二次進(jìn)入自循環(huán)
j = 2, 所以打印三次a

以此類推, 第三次打印兩次a

第四次打印一次a

所以我們總共進(jìn)行了4+3+2+1次操作，假設(shè)我們n為不確定的數(shù), 那么我們操作的總數(shù)就是(n-1)+(n-2)+(n-3)+...+3+2+1

細(xì)心的同學(xué)肯定發(fā)現(xiàn)了這是一個(gè)等差數(shù)列, 所以這個(gè)時(shí)間復(fù)雜度就是O(n*(n-1)/2), 根據(jù)我們上面學(xué)習(xí)的只要高階項(xiàng), 不要低階項(xiàng), 忽略系數(shù), 所以化簡后的時(shí)間復(fù)雜度是O(n²)

遞歸問題的時(shí)間復(fù)雜度計(jì)算

遞歸: 在函數(shù)的定義中使用函數(shù)自身

function cal(n) {
  if(n <= 0) {
    return 1
  }
  return cal(n - 1) + cal(n - 1)
}

我們把上面這個(gè)遞歸代碼進(jìn)行分解

由圖可知, 我們總操作數(shù)為2⁰+2¹+2²+2³+2⁴次, 我們依然假設(shè)n為不確定數(shù)
所以我們的總操作數(shù)為2⁰+2¹+2²+2³+2⁴+...+2^n-1+2ⁿ
細(xì)心的同學(xué)會(huì)發(fā)現(xiàn)這是一個(gè)等比數(shù)列, 根據(jù)等比數(shù)列求和公式可以得到時(shí)間復(fù)雜度為O(2ⁿ)

經(jīng)驗(yàn)性結(jié)論:
遞歸問題的時(shí)間復(fù)雜度通常(并不總是)看起來形如O(branches^depth)
其中branches指遞歸分支的總數(shù), depth指遞歸調(diào)用深度

時(shí)間復(fù)雜度計(jì)算 - 主定理

從數(shù)學(xué)的角度來說, 所有的復(fù)雜度我們都可以化成以下格式

我們以二分搜索為例

空間復(fù)雜度

• 時(shí)間復(fù)雜度不是衡量算法的唯一指標(biāo), 有時(shí)候還需要考慮空間復(fù)雜度
• 創(chuàng)建長度為n的數(shù)組, 需要O(n)的空間, 創(chuàng)建n*n的二維數(shù)組, 需要O(n²)的空間
• 一般情況下我們更側(cè)重于考慮時(shí)間復(fù)雜度, 甚至有時(shí)候需要用空間換時(shí)間

關(guān)于算法復(fù)雜度就說這么多了, 下次我們討論一個(gè)最常見的數(shù)據(jù)類型, 數(shù)組