|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 3 van 6 gevonden artikelen
| Titel: |
Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program |
| Auteur: |
Suchenek, Marek A. |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 120 (2012) nr. 1 pagina's 75-92 |
| Jaar: |
2012-09-07 |
| Inhoud: |
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 − 2s2(N) − e2(N), where s2(N) is the sum of all digits of the binary representation of N and e2(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: (2N − 1)$\lceil$lgN$\rceil$ − 2$\lceil$lgN$\rceil$+1 − 2s2(N) − e2(N) + 5. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 3 van 6 gevonden artikelen
| << vorige | volgende >> |