التفاصيل البيبلوغرافية
| العنوان: |
Expected Time Bounds for Selection. |
| المؤلفون: |
Floyd, Robert W., Rivest, Ronald L. |
| المصدر: |
Communications of the ACM; Mar1975, Vol. 18 Issue 3, p165-172, 8p, 3 Graphs |
| مصطلحات موضوعية: |
RANKING (Statistics), ALGORITHMS, COMPUTATIONAL complexity, COMPUTER programming, ELECTRONIC data processing, MEDIAN (Mathematics), MATHEMATICAL statistics, NUMERICAL analysis, MATHEMATICAL analysis |
| مستخلص: |
A new selection algorithm is presented which is shown to be very efficient on the average, both theoretically and practically. The number of comparisons used to select the ith smallest of n numbers is n + min (i,n- i) + o (n). A lower bound within 9 percent of the above formula is also derived. [ABSTRACT FROM AUTHOR] |
|
Copyright of Communications of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
