We assume for convenience that the set contains distinct numbers, although virtually everything that we do extends to the situation in which a set contains repeated values. This chapter addresses the problem of selecting the ith order statistic from a set of n distinct numbers. Thus, regardless of the parity of n, medians occur at i = ( n + 1)/2 and i = ( n + 1)/2. When n is even, there are two medians, occurring at i = n/2 and i = n/2 + 1. When n is odd, the median is unique, occurring at i = ( n + 1)/2. A median, informally, is the "halfway point" of the set. For example, the minimum of a set of elements is the first order statistic ( i = 1), and the maximum is the nth order statistic ( i = n). The ith order statistic of a set of n elements is the ith smallest element. Intro to Algorithms: CHAPTER 10: MEDIANS AND ORDER STATISTICS CHAPTER 10: MEDIANS AND ORDER STATISTICS
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |