Comment compter dans le pire des cas en temps linéaire?

Cette question et cette question m'ont fait réfléchir un peu. Pour trier un tableau de longueur avec éléments uniques dans , nous devons être en mesure de stocker le nombre de valeurs dans le tableau. Il y a quelques suggestions, mais je cherche un moyen de le faire dans le pire des cas, le temps linéaire. Plus précisement:$n$$k$$O(n + k \log k)$

Compte tenu de la liste de éléments avec éléments distincts, déterminer une liste de tuples de tous les éléments uniques tel que est le nombre d'éléments dans .$A$$n$$k$$U = \{(x_i, c_i)\}^k$$x_i \in A$$c_i$$x_i$$A$

Voici quelques idées (ratées) que j'ai eues et qui ont été suggérées:

1. Arbre de recherche binaire équilibré - Avec cela, il faudra pour insérer dans l'arbre et augmenter les valeurs. Après les insertions, nous pourrions faire une traversée d'arbre dans . Ainsi, le temps total sort à qui est trop lent.$O(\log k)$$O(k)$$O(n \log k)$
2. Hash Map - Avec cela, nous pouvons obtenir inserts attendus et donc temps prévu . Cependant, ce n'est toujours pas le pire cas .$O(1)$ $O(n)$ $O(n)$
3. Espace vide Mapping - Trouvez le minimum et maximum dans l' élément . Allouez (mais n'initialisez pas ) suffisamment de mémoire pour couvrir cette plage. Utilisez cette mémoire essentiellement comme une carte de hachage et incluez un hachage aléatoire afin que nous n'essayions pas d'accéder à la mémoire corrompue. Cette stratégie présente des problèmes. (1) Il est probabiliste avec une probabilité d'échec très très très faible, mais toujours pas garanti. L'utilisation de la mémoire comme celle-ci nous limite aux contraintes à virgule flottante ou entière.$A$
4. Tableaux associatifs - Il existe de nombreux autres tableaux associatifs qui peuvent être utilisés, similaires aux cartes de hachage et aux BST, mais je n'en trouve pas qui correspondent à ces contraintes.

Peut-être qu'il y a une méthode évidente qui me manque, mais je pense aussi que cela pourrait ne pas être possible. Quelles sont vos pensées?

C'est une belle question.

Dans le modèle de comparaison ou, plus généralement, dans le modèle d'arbre de décision algébrique, le problème de la distinction des éléments a une limite inférieure de $\Theta(n\log n)$complexité temporelle dans le pire des cas, comme dit dans cet article Wikipedia . Il n'y a donc pas d'algorithme pour compter des éléments distincts en temps linéaire dans le pire des cas, même sans compter les duplicités.

Cependant, il n'est pas clair si cela peut être fait dans un autre modèle de calcul. Cela semble peu probable dans tout modèle de calcul déterministe raisonnable.

Il existe des algorithmes randomisés dont le temps d'exécution prévu est $O(n)$; ou lorsque la probabilité que le temps d'exécution dure plus longtemps que$cn$ est exponentiellement petit $c$.

En particulier, choisissez au hasard une fonction de hachage à 2 universels, puis utilisez-la pour hacher tous les éléments du tableau. Cela permet d'atteindre les temps de fonctionnement indiqués, si vous choisissez correctement la longueur de sortie du hachage 2 universels.

Comme autre exemple, vous pouvez créer un algorithme randomisé dont le temps d'exécution le plus défavorable est $O(n)$ (il fonctionne toujours en temps linéaire, quoi qu'il arrive) et a une probabilité d'erreur d'au plus $1/2^{100}$. (Comment? Exécutez l'algorithme ci-dessus et terminez-le s'il s'exécute plus longtemps que$cn$ étapes pour certains choisis de manière appropriée $c$.) En pratique, cela suffit, car la probabilité que votre ordinateur émette la mauvaise réponse en raison d'un rayon cosmique est déjà beaucoup plus élevée que $1/2^{100}$.

Votre approche 3 peut être sécurisée en utilisant une solution pour l'exercice 2.12 de Aho, Hopcroft et Ullman (1974) The Design and Analysis of Computer Algorithms comme décrit, par exemple, dans Utilisation de la mémoire non initialisée pour le plaisir et le profit .

Fondamentalement, en plus de votre tableau d'éléments N avec les décomptes, vous avez deux tableaux d'éléments N et un décompte auxiliaire pour créer un ensemble clairsemé indiquant lesquels des décomptes sont valides.

En pseudocode de type C:

uint* a = malloc(n);
uint* b = malloc(n);
uint* c = malloc(n);
uint len = 0;

get_count(uint x) {
    uint idx = a[x];
    return idx >= 0 && idx < len && b[idx] == x ? c[idx] : 0;
}

increment_count(uint x) {
    uint idx = a[x];
    if (idx < 0 || idx >= len || b[idx] != x) {
        idx = len;
        len++;
        a[x] = idx;
        b[idx] = x;
        c[idx] = 0;
    }
    c[idx]++;
}

L'implémentation pratique de l'ensemble clairsemé est discutée dans cette réponse StackOverflow .