建堆O(n)时间复杂度证明

建堆复杂度先考虑满二叉树,计算完全二叉树建堆复杂度基本相同。

对满二叉树而言,第i层(根为第0层)有$2^i$个节点。由于建堆过程自底向上,以交换作为主要操作,因此第i层任意节点在最不利情况下,需要经过$(n-i)$次交换操作才能完成以该节点为堆根节点的建堆过程。因此,时间复杂度计算如下:

$T(n) = 2^0 * (n - 0) + 2^1 * (n - 1) + … + 2^n * (n - n) = sum((n - i) * 2^i)$

采用错位相减法:

  • 原式乘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$

上面推导中,n为层数编号(自0层根节点开始)。故总节点数为$(1 + 2 + 4 + … + 2^n) = 2^{n+1} - 1$。渐进时,忽略减1取$N = 2^{n+1}$。

$T(N) = 2^{n+1} - n - 2 = N * (1 - logN / N - 2 / N) ≈ N$

故时间复杂度为$O(N)$,得证。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×