Qu'est-ce que l'ordre des statistiques et le plus petit?

Question

J'ai un cours d'algorithme ce semestre. Tout va bien jusqu'à ce que j'aie atteint la conférence sur les statistiques de commande.

Voici la première diapositive de cette conférence:

Order Statistics 
Select the ith smallest of n elements (the 
element with rank i). 
• i = 1: minimum; 
• i = n: maximum; 
• i = ⎣(n+1)/2⎦ or ⎡(n+1)/2⎤: median. 
Naive algorithm: Sort and index ith element. 
Worst-case running time = Θ(n lg n) + Θ(1) 
= Θ(n lg n) 

Je ne comprends pas ce que sont les suivantes:

Qu'est-ce Statistiques Ordre?

Qu'est-ce que cela signifie sur le plus petit des n 0ents? S'il vous plaît j'ai besoin d'un exemple pour savoir ce qui est "ith" !!

Une explication simple à propos de ces? Tout ce que je sais, c'est que c'est lié à Divide and Conquer, parce que la diapositive suivante en parle :).

Answer 1

"Order statistics" est un nom de fantaisie pour "K-ième élément d'une séquence d'éléments N triés par ordre croissant". Le reste de la diapositive illustre simplement l'idée, en expliquant que les statistiques 1-ordre est le plus petit élément dans une séquence, statistiques n-ordre est le plus grand élément, n/2 statistiques d'ordre est médiane, et ainsi de suite.

Answer 2

la statistique d'ordre est la même que le plus petit élément d'un tableau. Par exemple disons que nous avons un tableau A [Size] = {3,4, -3, -2,0, 1,10,2,14} et nous voulons l'élément qui correspond au 4ème. La statistique d'ordre alors nous notre fonction ou programme renverrons la valeur 1. L'algorithme pour cela utilise une partition aléatoire et des appels récursifs à la fonction de sélection aléatoire.

Le pseudo-code est la suivante:

RSelect(Array[], p,r, i) 

if p == r 
     return A[p] 
q = RandomPartition(Array[],p,r) 
k = q - p + 1 
if i == k // case that the pivot is the answer 
return Array[q] 

else if i<k 
    return RSelect(Array,p, q-1,i) 
else 
    return RSelect(Array, q+1, r, i-k) 

L'algorithme est une division d'un algorithme de conquer qui utilise la récursivité pour briser le problème en choisissant un pivot aléatoire qui est fait dans la fonction de partition aléatoire pour aider à partitionner le tableau et éliminer les valeurs qui sont supérieures ou inférieures au pivot selon que la statistique ith Order est supérieure ou inférieure au pivot. Par exemple, si la statistique de l'ordre est inférieure au pivot, elle rejettera les valeurs supérieures au pivot. parce que la valeur de pivot retournée dans la fonction Partition est à sa place.