Мне нужно знать время Big O моего двоичного кода кучи и есть ли улучшения

Question

Мне нужно знать, каково время Big 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, которая является log base 2 из n .

Что касается улучшения, первое, что я вижу, это то, что когда heapsize равен нулю, ничего не происходит. это своего рода расточительные ресурсы ... так что, возможно, начните с 1. вот и все.