The MMIX Supplement: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth by Martin Ruckert

Author:Martin Ruckert [Ruckert, Martin]
Language: eng
Format: epub
Publisher: Addison-Wesley Professional
Published: 2015-07-12T16:00:00+00:00

Analysis of quicksort. The timing information shown with Program Q is not hard to derive using Kirchhoff’s conservation law (Section 1.3.3) and the fact that everything put onto the stack is eventually removed again. Kirchhoff’s law applied at Q2 also shows that

hence the total running time comes to

(25A − 2A ′ − 3A″ + 6B + 4C + 6D + 5E + 6N + 7S − 2S ′ + 6)υ + (3A + 2B + C + D + 2E + 2N − 2)μ

where

Because of symmetry, we may assume A″ = A ′″, A ′ = A − A ′, and S ′ = S − S ′. This simplifies the total running time to

(22.5A+6B+4C +6D+5E +6N +9S +7.5)υ+(3A+2B +C +D+2E +2N −2)μ.

[121]

Formulas (24) and (25) can be used to determine the best value of M on a particular computer. In MMIX’s case, Program Q requires 10(N + 1)HN+1 + (N + 1)f(M) − 27 cycles on the average, for N > 2M + 1, where

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.