我需要知道二进制堆代码的大O时间以及是否有改进

Question

我需要知道我的二进制堆代码的大O时间是什么,以及如何改进它？

这是代码:

public static void CreateMaxHeap(int[] a)
{
    for (int heapsize = 0; heapsize < a.Length; heapsize++)
    {
        int n, p;
        n = heapsize;
        while (n > 0)
        {
            p = (n - 1) / 2;
            if(a[n]>a[p])
                Swap(a,n,p);
            n = p;
        }
    }
} // end of create heap

Answer 1

这是O(nlgn)

迭代遍历O(n)的整个数组.但是每次迭代都会通过重复除以2返回数组.所以每次迭代都要将lgn添加到n,这是n的log base 2.

至于让它变得更好,我首先看到的是,当堆积为零时,没有任何反应.这有点浪费资源......所以也许从1开始.就是这样.