Thus, the same way Merge Short gets the same asymptotic running time, big O of N log N, as quick sorts gets on average. But now, in the worst case for every single input array. And it's still gonna run in linear time, big O of N time. That is, it uses no randomization whatsoever.
The selection algorithm, we cover here is deterministic. The ideas of this algorithm are just too cool not to tell you about, at least in optional video like this one. Well why bother given that our select is so good? Well frankly, I just can't help myself. For every input array of length N at the expected running time of R select is big O of N, where the expectation is over the random choices of the pivots that R select makes during execution, now in this optional video I'm going to teach you yet another algorithm for the selection problem.
But also it enjoys a satisfying theoretical guarantee. First its super practical, runs blazingly fast in practice. That algorithm which we called the R select algorithm was excellent in two senses. Previous videos covered an outstanding algorithm for the selection problem, the problem of computing the Ith statistic of a given array.
0 kommentar(er)
