您的位置: 首页  >  文章  >  堆排序中建堆过程的时间复杂度O(n)的证明

堆排序中建堆过程的时间复杂度O(n)的证明

分类: 文章 • 2025-03-12 14:15:09

下面是建立大根堆的代码

[cpp] view plain copy print?
  1. template <typename Type>  
  2. void CreateBigRootHeap(Type *array, int len)  
  3. {  
  4.     int i, j, k;  
  5.     Type temp;  
  6.   
  7.     for (i = (len - 1) / 2; i >= 0; --i)  
  8.     {  
  9.         temp = array[i];  
  10.         k = i;  
  11.   
  12.         for (j = i * 2 + 1; j < len; j = j * 2 + 1)  
  13.         {  
  14.             if (j < len - 1 && array[j] < array[j + 1])  
  15.                 j += 1;  
  16.   
  17.             if (temp > array[j])  
  18.                 break;  
  19.   
  20.             array[k] = array[j];  
  21.   
  22.             k = j;           
  23.         }  
  24.   
  25.         array[k] = temp;  
  26.     }  
  27. }  
现在对建立堆时所使用的时间复杂度为O(n)进行证明：

令堆所对应的完全二叉树的高度为h，节点的个数为n，现假定完全二叉树为满二叉树：即n = 2^h - 1,如下图（借用网上的图）所示

堆排序中建堆过程的时间复杂度O(n)的证明

有2^(h-2)个结点向下访问一次，2^(h-3)个结点向下访问2次，...1个结点向下访问h-1次(之前写错了，写成了h次，下面公式最后也应该是h-1， 因为好久了不好改了，抱歉)：

推导公式如下：

堆排序中建堆过程的时间复杂度O(n)的证明

在堆所对应的二叉树为非满二叉树时，复杂度是n同阶的。


转载http://blog.****.net/anonymalias/article/details/8807895

相关推荐