Lié à l'espace pour l'algorithme de sélection?

Question

Il y a un $ O pire cas bien connu (n) $ algorithme de sélection pour trouver k $ $ 'e Le plus grand élément dans un tableau d'entiers. Il utilise l'approche d'un de médiane de-terre-pleins pour trouver un assez bon pivot, les partitions du tableau d'entrée en place puis continue récursive en elle recherche de la k $ $ 'e plus grand élément.

Et si nous ne pouvions pas toucher le tableau d'entrée, la quantité d'espace supplémentaire serait nécessaire pour trouver k $ $ 'e plus grand élément de O $ (n) $ temps? Pourrait-on trouver k $ $ 'e plus grand élément de O $ (1) $ d'espace et de toujours garder le moteur d'exécution $ O (n) $? Par exemple, trouver le maximum ou un élément minimum prend O $ (n) $ temps et O $ (1) $ espace.

Intuitivement, je ne peux pas imaginer que nous pourrions faire mieux que O $ (n) $, mais l'espace est-il une preuve?

point Quelqu'un peut-il une référence ou venir avec un argument pourquoi le $ \ lfloor n / 2 \ rfloor $ -ième élément nécessiterait $ O (n) $ l'espace se trouve dans O $ (n) $ temps?

Answer 1

Il est un problème ouvert si vous pouvez le faire avec la sélection O $ (n) $ temps et O $ (1) $ cellules de mémoire supplémentaires sans changer l'entrée (voir here ). Mais vous pouvez venir assez près de cela.

Munro et Raman ont proposé un algorithme de sélection qui fonctionne dans O $ (n ^ {1+ \ varepsilon}) $ temps tout en utilisant seulement $ O (1 / \ varepsilon) $ de stockage supplémentaire (cellules). Cet algorithme laisse inchangé l'entrée. Vous pouvez choisir une petite $ \ varepsilon> 0 $.

À la base, l'algorithme de Munro et Raman fonctionne comme O $ classique (n) $ algorithme: Il maintient une gauche et droite lié ??(appelé Filtre ), qui sont deux éléments de rang connu. L'élément demandé est compris entre les deux filtres (sage rang). En choisissant un bon élément de pivot $ p $ nous pouvons vérifier tous les numéros contre les filtres et $ p $. Cela permet de mettre à jour les filtres et réduit le nombre d'éléments de gauche pour vérifier (sage rang). Nous le répétons jusqu'à ce que nous avons trouvé l'élément de demande.

Ce qui est différent de l'algorithme classique est le choix de $ p $. Soit $ A (k) $ soit l'algorithme qui permet de résoudre la sélection pour $ \ varepsilon = 1 / k $. L'algorithme $ A (k) $ divise le tableau en blocs de taille égale et identifie un bloc où de nombreux éléments sont, dont les rangs sont entre les filtres (existence par principe pigeon trous). Ce bloc sera ensuite analysé pour un bon élément de pivot avec l'aide de l'algorithme $ A (k-1) $. L'ancre de récursion est trivial $ (1) $ algorithme. La taille du bloc de droite (et faire le calcul) vous donne le temps et espace en cours d'exécution comme indiqué ci-dessus.

BTW, les algorithmes que vous recherchez, ont récemment été nommés algorithmes de travail constant espace .

Je ne suis pas au courant d'aucune borne inférieure.