It should be noted that the running time of this algorithm can be reduced to O(log n log log n) by applying some techniques that are outside the scope of this text. In addition, the problem can also be solved by first sorting the elements in Θ(log n) time and then selecting the required element in Θ(1) time. This Θ(log n) time sorting routine is also outside the scope of this book. In fact, Θ(n) optimal-cost algorithms for the selection problem on a PRAM are known. These algorithms are also outside the scope of this text.What I must do if I really need this out of scope algos & techniques ?
пятница, 23 ноября 2012 г.
Algorithms Sequential and Parallel
This book is standard of "strategy of default". Some real quotes (page 211):