Parlons d'algorithmes. Les débutants les perçoivent souvent comme quelque chose de difficile, de complexe et d'incompréhensible, et c'est en partie vrai, mais les algorithmes en sont la base. Et mieux vous connaissez les bases de votre spécialité, plus vous avez de chances d'y exceller.
Aujourd'hui, nous allons examiner un beau problème d'algorithme. Nous n'effrayerons pas les gens de travailler avec des algorithmes au tout début, donc dans notre analyse, il n'y aura pas d'arbres de segments étalés, pas d'optimisations assorties du problème du sac à dos ou de tests probabilistes de simplicité. Algos conviviaux.
Voici le défi: trouver la différence maximale entre voisins.
Un tableau de N entiers est donné. Il n'est en aucun cas ordonné et les nombres peuvent être répétés. Disons que nous l'avons trié et calculé la différence entre chaque paire d'éléments consécutifs. Il est nécessaire de trouver le maximum de cette différence et de le faire de la manière la plus optimale.
Compliqué? Vous pouvez essayer de faire cela avant de cliquer sur "Lire la suite", puis de vérifier la solution.
Alors allons-y. Différence maximale entre voisins.
Prenons un exemple:
Soit un tableau de N = 11 éléments.
Tout d'abord, résolvons le problème naïvement, cela aide souvent. Nous pouvons faire exactement ce que le problème exige de nous - trier les nombres et trouver la différence entre les éléments adjacents. La complexité de la solution variera en fonction du tri utilisé.
Si nous utilisonsqsortoumergesort, alors la complexité temporelle est . Si nous savons que les nombres sont distribués assez densément sur l'ensemble des entiers, alors nous pouvons utiliser le tri par comptage. Ensuite, nous obtenons , où U est la différence entre l'élément maximum et minimum. Le cas est relativement rare, mais il convient de rappeler cette possibilité.
Après le tri, nous obtenons un tableau:
Écrivons le tableau des différences:
Nous
obtenonsque la différence maximale est de 6.Réfléchissons maintenant, est-il possible de résoudre le problème plus rapidement? Lors de l'itération sur des paires d'éléments voisins, nous considérerons de nombreuses paires avec une petite différence. De telles paires ne pourront peut-être jamais faire la plus grande différence. En effet, dans le tableau trié, nous avons paire de nombres adjacents, que la différence entre le maximum et le minimum soit . Alors la plus grande différence doit avoir au moins . Cette estimation est vraie par le principe de Dirichlet.
Si les pigeons sont placés dans des cages et que le nombre de pigeons est supérieur au nombre de cages, alors au moins une des cages contient plus d'un pigeon.
9 cellules contiennent 10 pigeons, selon le principe de Dirichlet, au moins une cellule contient plus d'un pigeon ( Wikipedia )
Soit , ... , - i-ième élément du tableau trié. ensuite .
Si nous supposons que le maximum de tous D [i] est inférieur , puis la somme entière sera strictement inférieur à U, une contradiction.
Génial, nous avons obtenu une estimation inférieure pour la différence maximale! Essayons maintenant de localiser en quelque sorte les éléments qui sont trop proches les uns des autres - nous divisons le segment de l'élément minimum à l'élément maximum en demi-intervalles de longueur . Chaque élément tombera exactement dans un demi-intervalle. Nous obtiendrons une partition de tous les éléments en groupes disjoints, ils sont également appelés lots. Il est très simple de déterminer dans quel élément l'élément x appartient - vous devez calculer 1 + int ((x - a_min) / L) (nous numérotons à partir de un), où a_min est l'élément minimum dans le tableau A, il peut être trouvé en un seul passage le tableau d'origine. La seule exception sera l'élément maximum - il est préférable de créer des éléments avec une telle valeur dans un lot séparé. La figure montre la distribution de l'exemple décrit ci-dessus. Pour plus de clarté, faisons cela avec nos mains:
La distribution des lots est effectuée en temps linéaire et nécessite mémoire supplémentaire. Veuillez noter que les articles d'un lot ne peuvent pas donner la différence maximale entre deux articles. Nous avons spécialement sélectionné sa taille de cette manière.
Où peut-il y avoir deux éléments adjacents? Bien sûr, dans les lots non vides voisins! Par exemple, dans la figure, les éléments des troisième et sixième lots peuvent être placés sur une ligne dans un tableau trié, car les lots entre eux sont vides. Il est clair que seuls deux éléments seront adjacents - le maximum du 3ème lot et le minimum du 6ème. De même, les candidats pour une paire avec la différence maximale seront l'élément maximum du premier lot et l'élément minimum du troisième.
Écrivons toutes les paires d'éléments possibles qui peuvent donner la plus grande différence. Désignons par min (i) - l'élément minimum du i-ème groupe, par max (i) - l'élément maximum.
max (1) = -1 min (3) = 3
max (3) = 4 min (6) = 10
max (6) = 10 min (8) = 15
max (8) = 15 min (10) = 20
max (10) = 21 min (11) = 22
Nous avons identifié des paires qui méritent d'être considérées. En pratique, il est nécessaire de faire un seul passage sur tous les lots, de conserver le dernier lot non vide et la valeur maximale qu'il contient. Lorsque nous rencontrons le prochain lot non vide, nous y trouverons le minimum et essayerons de mettre à jour la réponse.
Nous serons heureux - nous avons résolu le problème à temps .
En fait, nous avons utilisé une idée assez connue et, en fait, avons fait les premières étapes du tri de poche, dans l'original, cela s'appelle letri au seau.
Les articles sont disposés dans des paniers, puis les articles de chaque panier sont triés
Dans le pire des cas, cela fonctionne pour , mais le temps de fonctionnement moyen avec un nombre suffisant de lots et une répartition uniforme des éléments est .
«Mais attendez, mais qu'en est-il de l'affaire quand , pourquoi ne l'avez-vous pas envisagé? »- demandera le lecteur attentif. Ce cas est dégénéré, nous ne l'avons donc pas considéré, mais faisons-le maintenant pour être complet.
Si la différence entre le minimum et le maximum est égale à zéro, alors la différence maximum est également nulle. En fait, c'est tout.