Recherche efficace du nombre d'éléments plus petits pour chaque élément d'un tableau

Je suis coincé sur ce problème:

Étant donné un tableau des premiers nombres naturels permutés de façon aléatoire, un tableau est construit, de telle sorte que est le nombre d'éléments de à qui sont plus petits que . $A$ $n$ $B$ $B(k)$ $A(1)$ $A(k-1)$ $A(k)$

i) Étant donné pouvez-vous trouver en temps ? ii) Étant donné pouvez-vous trouver en temps ? $A$ $B$ $O(n)$
$B$ $A$ $O(n)$

Ici, . Pour un exemple concret: $B(1) = 0$

| \begin{matrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \end{matrix} |

$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \\ \end{vmatrix}$

Quelqu'un peut-il m'aider? Merci.

algorithms arrays permutations damné
la source

J'ai trouvé ceci: le calcul des codages de permutation qui donne des algorithmes pour ces problèmes. Au moins, je pense que ce sont les mêmes problèmes.

O (n \log n)

$\mathcal O(n \log n)$

Realz Slaw

@Merbs, cet indice que vous avez donné signifie-t-il que vous avez une solution?

AJed

@AJed, cela signifie que j'ai un algorithme, mais il faut pour l'algorithme simple sans espace et si nous avons de l'espace. Pour le moment, je penche pour que ni l'un ni l'autre ne soit possible en et les deux soient le même algorithme.

O (n^{2})

$O(n^2)$

O (n \log n)

$O(n\log n)$

O (n)

$O(n)$

Merbs

@Merbs. Je pense que votre indice peut conduire à la bonne voie. im ayant une solution aussi (suivant votre indice). Je suppose qu'il y a une astuce dans l'analyse qui fait passer à .. Je pense que l'astuce est la connaissance que va de 1: seulement.

O (n)

$O(n)$

A

$A$

n

$n$

AJed

Cet article donne également un algorithme . Êtes-vous sûr qu'il existe un algorithme pour cela?

O (n \log n)

$\mathcal O(n \log n)$

O (n)

$\mathcal O(n)$

Realz Slaw

Réponses:

L'algorithme naïf pour déterminer partir de : $B$ $A$

Pour , déterminez la valeur de en comparant chaque à pour et en comptant ceux qui satisfont . $k=1,\dots,n$ $B(k)$ $A(i)$ $A(k)$ $i=1,\dots,k$ $A(i)<A(k)$

Cet algorithme compare à tous les autres ( fois), à autres, etc. donc le nombre total de comparaisons est . Mais ce n'est pas le mieux que nous puissions faire. Par exemple, en regardant , nous n'avons pas à faire de comparaisons! car il s'agit des premiers nombres naturels, et il est garanti (quelle que soit la permutation) que les nombres naturels inférieurs seront là. Et ? Au lieu de vérifier à , nous pourrions simplement vérifier . C'est: $A(1)$ $n-1$ $A(2)$ $n-2$ $\frac{(n-1)(n-2)}{2}$ $B(n)$ $B(n)=A(n)-1$ $n$ $n-1$ $B(n-1)$ $A(1)$ $A(n-2)$ $A(n)$

Pour , utilisez l'algorithme ci-dessus; pour utilisez l'algorithme inverse: déterminez en le définissant initialement sur puis en soustrayant pour chaque entrée pour inférieur à . $k=1, \dots,\frac{n}{2}$ $k=\frac{n}{2},\dots,n$ $B(k)$ $A(n)-1$ $1$ $A(i)$ $i=k+1,\dots,n$ $A(k)$

Cela prendrait étapes, qui est toujours . Notez également qu'en construisant partir de , si alors . $2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$ $O(n^2)$ $A$ $B$ $B(n)=A(n)-1$ $A(n)=B(n)+1$

Mais maintenant pour plus de finesse. Si nous avons droit à un espace supplémentaire ou à un tri sur place, nous pouvons trier les chiffres en les comparant. Par exemple:

| \begin{matrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 \end{matrix} |

$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & & \\ \end{vmatrix}$

Au lieu de les vérifier tous (ou de les vérifier dans l'ordre), nous pourrions utiliser la recherche binaire pour déterminer chaque . Cependant, le tri prend encore du temps . $B(k)$ $O(n\log n)$

Merbs
la source

Ce n'était que ma première idée; même si je me rends compte que le problème est plus intéressant que je ne l'avais initialement attribué. Et je n'ai pas encore eu l'occasion de lire les résultats de Realz Slaw, donc l'algorithme peut être désactivé.

Merbs

Plutôt que de déterminer chaque un à la fois, nous pouvons être tournés vers l'avenir et ne parcourir chaque numéro de qu'une seule fois ! Mais nous utiliserons espace: $B(k)$ $A$ $n$

| \begin{matrix} A & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & B \\ 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 4 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2 & 0 \\ 3 & 0 & 0 & 0 & 1 & 2 & 2 & 2 & 2 & 3 & 0 \\ 1 & 0 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 & 0 \\ 7 & 0 & 1 & 1 & 2 & 3 & 3 & 3 & 4 & 5 & 3 \\ 2 & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & 6 & 1 \\ 9 & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & 6 & 6 \\ 6 & 0 & 1 & 2 & 3 & 4 & 4 & 5 & 6 & 7 & 4 \\ 5 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 4 \end{matrix} |

$\begin{vmatrix} A & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & & B \\ 8 & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{0} & 1 & & 0\\ 4 & & 0 & 0 & 0 & \color{red}{0} & 1 & 1 & 1 & 1 & 2 & & 0\\ 3 & & 0 & 0 & \color{red}{0} & 1 & 2 & 2 & 2 & 2 & 3 & & 0\\ 1 & & \color{red}{0} & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 & & 0\\ 7 & & 0 & 1 & 1 & 2 & 3 & 3 & \color{red}{3} & 4 & 5 & & 3\\ 2 & & 0 & \color{red}{1} & 2 & 3 & 4 & 4 & 4 & 5 & 6 & & 1\\ 9 & & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & \color{red}{6} & & 6\\ 6 & & 0 & 1 & 2 & 3 & 4 & \color{red}{4} & 5 & 6 & 7 & & 4\\ 5 & & 0 & 1 & 2 & 3 & \color{red}{4} & 5 & 6 & 7 & 8 & & 4\\ \end{vmatrix}$

Nous pourrions gagner encore plus de temps en ne mettant pas à jour ceux qui ont déjà été déterminés (c'est-à-dire qu'il est inutile de mettre à jour après la première étape), mais dans le pire des cas, nous devons encore mettre à jour fois $8$ $\frac{(n)(n+2)}{2}$

Merbs
la source

I et II peuvent être résolus en utilisant #next_greater_element que j'ai expliqué ici . mais c'est un peu plus difficile que le problème, mais avant la solution, vous devez apprendre le prochain élément plus important:

considérons que nous avons un vecteur pour chaque élément de nommez-le pour l'élément . maintenant, exécutez une fois l'algorithme supérieur suivant, de droite à gauche, mais sauf pour définir l'élément dans son index d'élément supérieur suivant, appuyez sur les éléments dont est leur prochain élément supérieur. puis parcourez le tableau de gauche à droite, puis où est la taille du vecteur son car chacun le plus grand algorithme suivant est et aussi itération est $A$ $S_i$ $i$ $i$ $A$ $S_i$ $i$ $B[i]=\sum_{j=0}^x (S_i[j]+1)$ $x$ $S_i$ $\Theta(n)$ $\Theta(n)$ $\Theta(n)$

la deuxième partie est également similaire en notant que nous pouvons obtenir la valeur de l'élément le plus à droite dans EDIT: ma solution est fausse il semble qu'elle n'a pas de solution $O(1)$ $o(n)$

Ali.Mollahoseini
la source