建堆復(fù)雜度先考慮滿(mǎn)二叉樹(shù)，計(jì)算完全二叉樹(shù)建堆復(fù)雜度基本相同。
對(duì)滿(mǎn)二叉樹(shù)而言，第i層(根為第0層)有2^i個(gè)節(jié)點(diǎn)。由于建堆過(guò)程自底向上，以交換作為主要操作，因此第i層任意節(jié)點(diǎn)在最不利情況下，需要經(jīng)過(guò)(n-i)次交換操作才能完成以該節(jié)點(diǎn)為堆根節(jié)點(diǎn)的建堆過(guò)程。因此，時(shí)間復(fù)雜度計(jì)算如下：
T(n) = 2^0 * (n - 0) + 2^1 * (n - 1) + ... + 2^n * (n - n) = sum((n - i) * 2^i)
采用錯(cuò)位相減法：
- 原式乘2得：
T(n) * 2 = 2^1 * (n - 0) + 2^2 * (n - 1) + ... + 2^(n+1) * (n - n)= sum((n - i) * 2^(i+1))- 原式如下：
T(n) = 2^0 * (n - 0) + 2^1 * (n - 1) + ... + 2^n * (n - n)= sum((n - i) * 2^i)- 相減得：
2T(n) - T(n) = -n + 2^1 + 2^2 + ... + 2^n = 2 * (1 - 2^n) / (1 - 2) - n= 2^(n+1) - 2 - n
上面推導(dǎo)中，n為層數(shù)編號(hào)（自0層根節(jié)點(diǎn)開(kāi)始）。故總節(jié)點(diǎn)數(shù)為(1 + 2 + 4 + ... + 2^n) = 2^(n+1) - 1。漸進(jìn)時(shí)，忽略減1取N ＝ 2^(n+1)。
T(N) = 2^(n+1) - n - 2 = N * (1 - logN / N - 2 / N) ≈ N
故時(shí)間復(fù)雜度為O(N)，得證。
