Baisse théorique limitée de la recherche du nombre d'occurrences d'un entier cible dans une matrice triée

Question

Compte tenu d'une éventail de nombres entiers triés et d'un entier cible, trouvez le nombre d'occurrences de l'entier cible.

Il est bien connu qu'une recherche binaire a une complexité de temps $ o (\ lg n) $ où $ n$ est la taille de la matrice. Par exemple, étant donné un tableau $ [1,2,3,3,4,5] $ et une cible 3 $,$ L'algorithme doit renvoyer $ 2 $ car il y a deux copies de $ 3 $ dans le tableau.

Question: Y a-t-il un algorithme plus rapide qui a moins de complexité de temps que $ o (\ lg n)? $ Sinon, y a-t-il une preuve pour prouver que $ \ oméga (\ lg n) $ est la limite inférieure théorique?

Answer 1

Le problème nécessite $ \ oméga (\ journal n) $ accès à la mémoire Même si vous êtes promis que l'entier cible apparaisse au plus une fois. Vous pouvez le prouver à l'aide d'un argument adversaire.

dire que la cible est zéro. Si le premier accès au tableau est laissé du centre, répondez $ - 1 $ et définissez mentalement les éléments à gauche pour être $ - 2, -3, \ ldots $ . Si le premier accès est à droite du centre, répondez $ + 1 $ et définissez mentalement les éléments à droite pour être $ 2 , 3, \ ldots $ .

Supposons que le premier accès était à droite du centre, disons la position $ i $ et considérez le deuxième accès. Si c'est à la droite du premier accès, vous savez déjà quoi répondre. Sinon, il y a deux cas. Si la position accessible $ j $ est inférieure à $ i / 2 $ , réponse $ - 1 $ (et remplissez les éléments à gauche). Si c'était plus que $ I / 2 $ , réponse $ + 1/2 $ (et remplissez éléments à la droite de positionner $ i $ ).

Continuer de cette manière, à chaque étape, le nombre de positions pouvant contenir l'élément cible est de moitié réduit de moitié à chaque étape. Enfin, lorsque un seul élément est toujours en jeu, l'algorithme ne peut pas savoir si la matrice contient l'élément cible ou non. Il faut $ \ log_2 n $ étapes pour atteindre cette étape.

Le précédent indique en fait que la recherche binaire est optimale pour la recherche d'une matrice triée.

Answer 2

Il y a $ n $ réponses possibles.Chaque comparaison vous donne au plus un peu d'informations.Vous avez besoin d'au moins $ \ lg n $ bits d'informations pour décrire la réponse, vous aurez donc besoin d'au moins $ \LG N $ Comparaisons.