Trouver le k plus petit élément d'une séquence donnée uniquement avec O (k) mémoire O (n) temps

Supposons que nous lisions une séquence de $n$ nombres, un par un. Comment trouver le $k$ plus petit élément simplement en utilisant la mémoire de cellule $O(k)$ et en temps linéaire ( $O(n)$ ). Je pense que nous devrions enregistrer les premiers $k$ termes de la séquence et lorsque nous obtenons le $k+1$ 'ème terme, supprimer un terme qui nous assure qu'il ne peut pas être le $k$ ième élément le plus petit, puis enregistrer $k+1$ ' ème terme. Nous devrions donc avoir un indicateur qui montre ce terme inutilisable à chaque étape et cet indicateur devrait être mis à jour à chaque étape rapidement. J'ai commencé avec "max"; mais il ne peut pas se mettre à jour rapidement; Signifie que si nous considérons max, alors lors de la première suppression, nous manquons le max et nous devons rechercher max dans $O(k)$ et sa cause $(n-k)\times O(k)$ temps qu'il n'est pas linéaire. Peut-être devrions-nous enregistrer les premiers $k$ termes de la séquence de manière plus intelligente.

Comment puis-je résoudre ce problème?

data-structures search-algorithms quicksort Shahab_HK
la source

Êtes-vous intéressé par un algorithme en ligne, ou un algorithme le ferait-il?

Yuval Filmus

k = θ (n)

$k = \theta(n)$ vous pouvez le faire en utilisant un algorithme de statistiques d'ordre. Si

k = o (n)

$k = o(n)$ vous pouvez le faire

O (k)

$O(k)$ mémoire et

O (n \log k)

$O(n\log k)$ utilisant n'importe quel arbre à hauteur équilibrée.

Shreesh

Cela s'appelle le problème de sélection en.wikipedia.org/wiki/Selection_algorithm

xavierm02

Il existe des algorithmes linéaires sur place, que vous pouvez rechercher sur Google, mais ils sont quelque peu compliqués.

Yuval Filmus

@ xavierm02 ce n'est pas le problème de sélection à l'identique. Parce qu'il y a une contrainte de limite de mémoire.

Shahab_HK

Réponses:

Créez un tampon de taille . Lire éléments du tableau. Utilisez un algorithme de sélection à temps linéaire pour partitionner le tampon de sorte que les plus petits éléments soient les premiers; cela prend du temps . Maintenant, lisez dans un autre éléments de votre tableau dans le tampon, en remplaçant les plus grands éléments du tampon, partitionnez le tampon comme précédemment et répétez. $2k$ $2k$ $k$ $O(k)$ $k$ $k$

Cela prend temps et espace. $O(k * n/k) = O(n)$ $O(k)$

jbapple
la source

+1, cela correspond aux asymptotiques demandées. Cela étant dit, je ne pense pas que ce soit plus rapide que de faire un seul algorithme de sélection en temps linéaire ... sauf lorsque

est une petite constante, cela fournit une perspective intéressante. Par exemple, pour

cet algorithme produit la fonction.

k

$k$

k = 1

$k = 1$ min

orlp

Parfois, l'algorithme de sélection linéaire-temps utilise trop d'espace. Par exemple, il ne convient pas pour une utilisation dans un contexte de streaming ou lorsque le tableau d'entrée est immuable.

jbapple

Ce sont des points valables.

orlp

$O(k)$ $O(n \log k)$ $k$ $O(k)$ $O(\log k)$ $O(k + n\log k)$ $O(n \log k)$

$O(\log n)$ $O(n)$ $k$ $k$

$O(\log n)$ $O(k)$ $O(\log n)$ $2^{64}$ $\log 2^{64}= 64$ $k$ $n$

orlp
la source

O (n \times \log min (k, n - k))

$O(n \times \log\min (k, n - k))$

@ xavierm02 = . Preuve: le pire des cas pour est . Le pire des cas pour est . Ils sont les mêmes à l'intérieur d'un facteur constant, donc = .

O (m i n (k, n - k))

$O(min(k, n-k))$

O (k)

$O(k)$

k

$k$

n

$n$

m i n (k, n - k)

$min(k, n-k)$

\frac{n}{2}

$n \over 2$

O (m i n (k, n - k))

$O(min(k, n-k))$

O (k)

$O(k)$

orlp

@ xavierm02 Cela étant dit, c'est toujours une belle accélération :)

orlp

u_{n, k} = k

$u_{n,k}=k$ est mais ce n'est pas . Supposons que ce soit le cas. Ensuite, il y a du et du sorte que pour chaque , nous avons , ce qui est clairement faux (car nous pouvons prendre Donc .

O (k)

$O(k)$

O (min (k, n - k))

$O(\min (k, n-k))$

C

$C$

M

$M$

M \leq k \leq n

$M\le k\le n$

k \leq C (n - k)

$k\le C (n-k)$

n = k \to + \infty) .

$n=k \to +\infty).$

O (min (k, n - k)) ⊊ O (k)

$O(\min(k, n-k))\subsetneq O(k)$

xavierm02

@ xavierm02 Je ne connais pas votre notation . Pour être juste, je ne suis généralement pas assez familier avec la notation multidimensionnelle big- , surtout si l'on considère que les dimensions ne sont pas indépendantes.

u_{n, k}

$u_{n, k}$

O

$O$

n, k

$n, k$

orlp