Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: sum of digits

Sortuj według:

Ogranicz wyniki do:

Elementary Yet PreciseWorst-Case Analysis of Floyd's Heap-Construction Program

Suchenek M. A.

Fundamenta Informaticae

2012

Vol. 120, nr 1

75-92

The worst-case behavior of the heap-construction phase of Heapsort escaped mathematically precise characterization by a closed-form formula for almost five decades. This paper offers a proof that the exact number of comparisons of keys performed in the worst case during construction of a heap of size N is: 2N-2s_2(N) - e_2(N); where s_2(N) is the sum of all digits of the binary representation of N and e_2(N) is the exponent of 2 in the prime factorization of N. It allows for derivation of this best-known upper bound on the number of comparisons of Heapsort: [formula]