Comment trouver le kième élément le plus grand dans un tableau non trié de longueur n dans O (n)?

Question

Je crois qu'il y a un moyen de trouver le kième élément le plus grand dans un tableau non trié de longueur n dans O (n). Ou peut-être c'est "attendu" O (n) ou quelque chose. Comment peut-on le faire?

Answer 1

Cela s'appelle de trouver le k-ième ordre statistique. Il y a une très simple algorithme randomisé (appelé quickselect) en prenant O(n) moyenne de temps, et une assez compliqué non randomisées algorithme prenant O(n) pire des cas le temps. Il y a peu d'info sur Wikipédia, mais il n'est pas très bon.

Tout ce dont vous avez besoin est dans ces diapositives powerpoint. Juste pour en extraire l'algorithme de base de l' O(n) pire cas de l'algorithme:

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group's median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

Il est également très bien détaillé dans l'Introduction aux Algorithmes livre de Cormen et coll.

Answer 2

Si vous voulez un vrai O(n) de l'algorithme, par opposition à l' O(kn) ou quelque chose comme ça, alors vous devriez utiliser quickselect (il s'agit essentiellement de quicksort où vous vous débarrassez de la partition que vous n'êtes pas intéressés). Mon prof a un excellent article, avec l'analyse de l'exécution: (référence)

Le QuickSelect algorithme trouve rapidement de la k-ième plus petit élément d'un tableau non trié de n - éléments. C'est un RandomizedAlgorithm, nous avons donc calculer le pire des cas attendus de temps de fonctionnement.

Voici l'algorithme.

QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))
  else
    # it's equal to the pivot
    return pivot

Qu'est-ce que le temps d'exécution de cet algorithme? Si l'adversaire retourne les pièces de monnaie pour nous, on peut trouver que le pivot est toujours l'élément le plus large et k est toujours 1, ce qui donne un temps d'exécution de

T(n) = Theta(n) + T(n-1) = Theta(n

Mais si les choix sont en effet aléatoire, le temps d'exécution est donné par

2

lorsque nous faisons les pas entièrement hypothèse raisonnable que la récurrence toujours terres dans la plus grande des ) ou T(n) i=1 to nT(max(i, n-i-1)).

Let's suppose que c' A1 pour certains A2. Puis, nous avons

T(n) <= an

et maintenant, en quelque sorte, nous devons obtenir de l'effroyable somme sur la droite du signe plus à absorber l' a sur la gauche. Si nous avons juste lié comme T(n) i=1 to nT(max(i-1, n-i)) = cn + (1/n) ∑, nous obtenons environ _{i=1 to floor(n/2)}. Mais c'est trop gros il n'y a pas de place pour serrer dans une extra - T(n-i) + (1/n) ∑. Donc, nous allons étendre la somme en utilisant l'arithmétique de la série formule:

i=floor(n/2)+1 to n

où l'on prend avantage de n être "suffisamment grand" pour remplacer le moche T(i) i=floor(n/2) to n T(i) i=floor(n/2) to n ai facteurs ayant la plus propre (et plus petit) cn. Maintenant, nous pouvons continuer avec

2(1/n) ∑

fournis _{i=n/2 to n}.

Cela donne an. C'est clairement 2(1/n)(n/2)an = an, nous obtenons donc T(n) = Theta(n).

Answer 3

Les mots clés que vous recherchez sont l' algorithme de sélection : Wikipédia énumère un certain nombre de façons différentes de le faire.

Answer 4

Un rapide Google sur cela («kth plus grand tableau d'éléments») a retourné ceci: http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17

 "Make one pass through tracking the three largest values so far." (it was specifically for 3d largest)
 

et..

 Build a heap/priority queue.  O(n)
Pop top element.  O(log n)
Pop top element.  O(log n)
Pop top element.  O(log n)

Total = O(n) + 3 O(log n) = O(n)
 

Answer 5

Vous aimez le tri rapide. Choisissez un élément au hasard et tout pousser plus haut ou plus bas. À ce stade, vous saurez quel élément vous avez réellement choisi, et si c'est le kième élément que vous avez terminé, sinon vous répétez avec la poubelle (plus haut ou plus bas), que le kième élément tomberait. Statistiquement parlant, le temps il faut trouver le kième élément croissant avec n, O (n).